传送门 此题思路还是非常巧妙的。 考虑我们莫队的 Add 函数，本质上是往原本的区间里面加上一个数，然后算这个数的贡献。 比如说我们设 f(x,[l,r])f(x,[l,r])f(x,[l,r]) 为 ∑i=lr[cnt(x⊕a[i])=k]\sum _{i=l}^r [cnt(x \oplus a[i])=k]∑i=lr​[cnt(x⊕a[i])=k]（中括号里面为真时，值为 1，cntc...

其实这是一篇咕了很久的学习笔记。 本人比较喜欢莫队这种根号算法。 以上是博主瞎扯淡，下面正文开始。 莫队基本原理 何为莫队，莫队可不是一个队列，他是以集训队大佬莫涛为名的暴力算法（又称对询问分块）。 其实思路比较简单，我们现在得到了查询[l1,r1][l_1,r_1][l1​,r1​]的答案，想要通过比较少的代价获得[l2,r2][l_2,r_2][l2​,r2​]的答案，怎么办。 一个...

传送门 首先建议看一下这篇博客，学习一下回滚莫队和撤销的奇巧淫技。 0≤ai≤1090 \le a_i \le 10^90≤ai​≤109，蜃是恐怖，但是发现如果答案ans>n+1ans > n+1ans>n+1，说明1...n+11 ... n+11...n+1所有数都出现过，但是我们只有nnn个数，所以矛盾，于是读入的时候这样处理即可。 1a[i]=min(n+1,re...

BZOJ GDOI 首先，安利一下巨佬ypy的博客，我的思路是参照ypy博客的。 先说一下我的思路，首先，将问题抽象为往一个数轴上面放111，求最长连续111的值。 Sol1: 线段树维护连续111的最大值，代码非常简单，维护区间连续111最大值maxnmaxnmaxn，从左边开始连续111最大值lmaxlmaxlmax，从右边开始连续111最大值rmaxrmaxrmax，区间111的和v...

传送门 首先，如果这道题用的是普通的莫队，那么删除元素的时候，可能出现次数最大的那个元素的出现次数被减少至小于出现次数第二大的那个元素的出现次数，此时，你就没法知道出现次数第二大的元素的值，就咕咕了。 当然你也可以用一个set\rm setset搞，但是估计会TLE\rm TLETLE 这里要介绍一种莫队，叫做回滚莫队。 先考虑莫队的排序方式，我们把整个序列分块，以左端点所在的块的编号为第一...

洛谷 GDOI 本质和这道题P4867是一样的，先看一看这篇博客的代码，魔改一下就可以AAA了。 魔改也非常简单，只要再开一个分块，有数加进来就加进分块的数组里面，不用判重。 然后，更加简单的是，这题竟然不用离散化也能AAA，数据过水。 123456789101112131415161718192021222324252627282930313233343536373839404142434...

BZOJ GDOI 一句话题意：给你l,rl,rl,r，求a[l],a[l+1]...a[r]a[l],a[l+1]...a[r]a[l],a[l+1]...a[r]逆序对个数。 按照套路，我们先离散化。 然后考虑加入一个数会对逆序对做出多少贡献，先考虑我们从左边加入一个数，如图： 显然，只有严格小于他的数才会对答案产生贡献。 再考虑在右边加入一个数，如图： 显然，只有严格大于他的数才会...

洛古 GDOI 首先，看见“权值∈[a,b]\in [a,b]∈[a,b]的权值的种类数。”这样的话就要想到莫队。 我们有一个比较显然的树状数组做法，每次加进一个数，如果没有出现，那么加进树状数组，删除也是类似，最后前缀和相减统计一下即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424...

首先，乖♂乖♂交♂出数据生成器： 12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;inline int gen(){ return (rand()<<15)|(rand());}int main(){ srand(ti...

传送门 莫队是一种多么优美的算法，肿么能不用莫队呢？ 只要记录区间出现次数超过222的数就可以搞定了（代码中是cnt2cnt2cnt2）。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <bits/stdc++...