莫队 – Tgotp-Blog

4241: 历史研究

回滚莫队 ...
就是说对于这题来说,添加容易,但是删除困难,那么就不考虑删除,即把左右端点分别放在块的两边,中间的是可以直接处理出来,然后块中的暴力更新,完了以后再变更为更新前的状态即可.
复杂度O(n\sqrt {n})
c++代码如下:
[crayon-5b50ab589b76[......]

Read more

5301: [Cqoi2018]异或序列

看完题,容易想到把求一段区间改成求 前r的异或和 ^ 前l-1的异或和 等于k, 那么这个东西发现可以直接用莫队统计,没了.

c++代码如下:

 

2120: 数颜色

细节wa成傻逼。

带修莫队裸题。

简单来说就是对普通莫队多一个维护时间,然后每次更新之前先维护一下时间对答案的影响,搞定

c++代码如下:

 

tyvj测试

很不爽啊。。。

day1 60 + 100 + 10 = 170

day2 100 + 40 + 80 = 220

总分390

update:然后吐槽一下:tyvj的测评姬大概烂破了天际。。。能测一个小时的代码我还是第一次见。。。莫名其妙的System Error真[......]

Read more

3585: mex

算法一:莫队算法,大力艹一艹就过了。

速度堪忧。。。显而易见是下面那个。。。

c++代码如下:

算法二:主席树

对于权值建树,离散化位置。

更新每个点最后出现的位置,如果左子树最后出现的位置小于l,肯定能过[......]

Read more

1878: [SDOI2009]HH的项链

莫队,莫队,好写的莫队。

十分钟你买不了吃亏,买不了上当。

所以能不写线段树就不写呗。

莫队 艹 一 艹 就过了。。。

当然其实还可以写离线线段树的或者离线树状数组,不写了不写了,太长了233

c++代码如下:
[crayon-5b50ab589db2f3296551[......]

Read more

小z的袜子

莫队算法入门题,关于这道题的解释到处都是,这里只放代码了。