优雅的暴力——莫队算法学习笔记

eq1E5BLQZw7W

一、问题引入

当有一道题每次问你一个区间的某某东西，而这个东西不可合并（不可线段树）不可差分（不可树状数组）分块后不好合并/无法合并（不可分块），但是支持离线并且任意一个区间能通过扩张和收缩得到其它区间的答案，那么这道题就可以莫队。
二、什么是莫队

首先，如果有一道区间可扩张收缩的题（不需要支持离线），你是不是可以先求出第一个区间的答案，然后通过左右端点的扩张和收缩求出其它区间的答案，但是你会发现最坏时间复杂度跟暴力的 \(O(qn)\) 一样，但是这个时候神奇的事情就来了，我们给它将询问离线一下，然后通过一种神奇的排序之后，它的时间复杂度就变成了 \(O((q+n) \sqrt n)\) 了！这个神奇的排序是什么呢，就是先将 \(1\) 到 \(n\) 的所有点分个块，然后排序时先按照 \(l\) 所在的块从小到大排序，如果有两个 \(l\) 相等，再按照 \(r\) 的从小到大排序。
三、如何证明莫队时间复杂度

首先你会发现左指针单次移动如果是在同一个块，那么单次移动时间复杂度为 \(O(\sqrt n)\)，因为一个块的大小最多为 \(\sqrt n\)，而左指针又不能移出这个块，然后如果是不同一个块的移动，因为每次最多移动 \(O(\sqrt n)\) 步，所以单次移动时间复杂度为 \(O(\sqrt n)\)，然后开始考虑总移动，你就会发现时间复杂度为 \(O(q \sqrt n+n)\)，\(O(q\sqrt n)\) 是同一个块内移动的总复杂度（因为要移动 \(q\) 次嘛，所以就是 \(O(q \times \sqrt n) = O(q \sqrt n)\)），然后 \(O(n)\) 指的是不同一个块的移动的总时间复杂度，因为发生这种情况只会有 \(O(\sqrt n)\) 次，所以总时间复杂度为 \(O(\sqrt n \times \sqrt n) = O(n)\)，然后考虑右指针移动，你会发现根据莫队的排序右指针块内单调递增，但是跨越块就不一定掉递增，那么你会发现跨越块的行为最多只会出现 \(O(\sqrt n)\) 次，而每次最坏移动 \(O(n)\) 步，所以总时间复杂度为 \(O(\sqrt n \times n+n) = O(n \sqrt n+n) = O(n \sqrt n)\)，所以最后时间复杂度为 \(O((n+q) \sqrt n)\)，当然，在计算过程中，我们省掉了好几个常数，所以莫队的常数也是有点大的。
四、莫队板子

#include<bits/stdc++.h>using namespace std;const int N = 5e4+5;//可自由变动struct node{        int l;        int r;        int id;}b[N];int a[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x){        //扩张区间}void del(int x){        //收缩区间}int ans[N];signed main(){        int n,_;        scanf("%d %d",&n,&_);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%d",&a);        }        for(int i = 1;i<=_;i++)        {                scanf("%d %d",&b.l,&b.r);                b.id = i;        }        sort(b+1,b+_+1,cmp);        for(int i = 1,l = 1,r = 0;i<=_;i++)//至于这里为什么l = 1,r = 0是因为老师说这样可以防止迷之错误        {                while(l>b.l)//老师还说一定要先扩张再收缩，可以防止l>r的情况                {                        add(--l);                }                while(r<b.r)                {                        add(++r);                }                while(l<b.l)                {                        del(l++);                }                while(r>b.r)                {                        del(r--);                }                ans[b.id] = sum;        }        return 0;}注意：这只是一个板子，里面的内容可以随机应变。
五、莫队习题讲解

P3901 数列找不同

很基础的一个莫队，把莫队板子套过来填上 add 和 del 函数就行了。
代码：
#include<bits/stdc++.h>using namespace std;const int N = 1e5+5;struct node{        int l;        int r;        int id;}b[N];int a[N];int tong[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x){        if(tong[a[x]] == 1)    {        sum++;    }        tong[a[x]]++;}void del(int x){        tong[a[x]]--;        if(tong[a[x]] == 1)    {        sum--;    }}int ans[N];signed main(){        int n,_;        scanf("%d %d",&n,&_);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%d",&a);        }        for(int i = 1;i<=_;i++)        {                scanf("%d %d",&b.l,&b.r);                b.id = i;        }        sort(b+1,b+_+1,cmp);        for(int i = 1,l = 1,r = 0;i<=_;i++)        {                while(l>b.l)                {                        add(--l);                }                while(r<b.r)                {                        add(++r);                }                while(l<b.l)                {                        del(l++);                }                while(r>b.r)                {                        del(r--);                }                ans[b.id] = sum;        }        for(int i = 1;i<=_;i++)        {                printf("%s\n",ans?"No":"Yes");        }        return 0;}AT_abc293_g [ABC293G] Triple Index

比上一道题稍难一点，我们考虑 \(num_x\) 表示在当前区间 \(x\) 出现了多少次，那么我们考虑 \(num_x\) 变成 \(num_x+1\) 会对答案造成什么影响，发现造成的影响就是 \(C_{num_x+1}^3-C_{num_x}^3\)，\(C_{num_x+1}^3 = \frac{(num_x+1)num_x(num_x-1)}{3!} = \frac{(num_x+1)num_x(num_x-1)}{6}\)，\(C_{num_x}^3 = \frac{num_x(num_x-1)(num_x-2)}{3!} = \frac{num_x(num_x-1)(num_x-2)}{6}\)，\(C_{num_x+1}^3-C_{num_x}^3 = \frac{(num_x+1)num_x(num_x-1)}{6}-\frac{num_x(num_x-1)(num_x-2)}{6} = \frac{num_x((num_{x}-1)(num_{x}+1-(num_{x}-2)))}{6} = \frac{num_x((num_{x}-1)(num_{x}+1-num_{x}+2))}{6} = \frac{num_x(3(num_{x}-1))}{6} = \frac{3num_x(num_x-1)}{6} = \frac{num_x(num_x-1)}{2}\)，删除操作也是一样的推法，然后就正常的套莫队板子就行了。
十年 OI 一场空，不开 long long 见祖宗！
代码：
#include<bits/stdc++.h>using namespace std;#define int long long const int N = 2e5+5;struct node{        int l;        int r;        int id;}b[N];int a[N];int tong[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x){    sum+=tong[a[x]]*(tong[a[x]]-1)/2;        tong[a[x]]++;}void del(int x){        tong[a[x]]--;        sum-=tong[a[x]]*(tong[a[x]]-1)/2;}int ans[N];signed main(){        int n,_;        scanf("%lld %lld",&n,&_);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%lld",&a);        }        for(int i = 1;i<=_;i++)        {                scanf("%lld %lld",&b.l,&b.r);                b.id = i;        }        sort(b+1,b+_+1,cmp);        for(int i = 1,l = 1,r = 0;i<=_;i++)        {                while(l>b.l)                {                        add(--l);                }                while(r<b.r)                {                        add(++r);                }                while(l<b.l)                {                        del(l++);                }                while(r>b.r)                {                        del(r--);                }                ans[b.id] = sum;        }        for(int i = 1;i<=_;i++)        {                printf("%lld\n",ans);        }        return 0;}P1494 [国家集训队] 小 Z 的袜子

上一道题的弱化版，似乎没什么好说的，就是三元组换成了二元组。
依旧是……十年 OI 一场空，不开 long long 见祖宗！
我们是要拿总数除以可能搭配的二元组数量，所以如果你依旧只使用 \(ans\) 数组存储二元组数量，那么请你在回答每个询问时，开一个 \(num\) 数组，表示原始询问编号对应的排序后的编号，不然就会像我一样调一小时……
千万不要忘了题目中的 \(l = r\) 的情况！！
代码：
#include<bits/stdc++.h>using namespace std;#define int long long const int N = 5e4+5;struct node{        int l;        int r;        int id;}b[N];int a[N];int tong[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x){        sum+=tong[a[x]];        tong[a[x]]++;}void del(int x){        tong[a[x]]--;        sum-=tong[a[x]];}int ans[N];int num[N];signed main(){        int n,_;        scanf("%lld %lld",&n,&_);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%lld",&a);        }        for(int i = 1;i<=_;i++)        {                scanf("%lld %lld",&b.l,&b.r);                b.id = i;        }        sort(b+1,b+_+1,cmp);        for(int i = 1,l = 1,r = 0;i<=_;i++)        {                while(l>b.l)                {                        add(--l);                }                while(r<b.r)                {                        add(++r);                }                while(l<b.l)                {                        del(l++);                }                while(r>b.r)                {                        del(r--);                }                ans[b.id] = sum;                num[b.id] = i;        }        for(int i = 1;i<=_;i++)        {                if(b[num].l == b[num].r)//记得这里很重要，不然就10分                {                        printf("0/1\n");                        continue;                }                int yue = __gcd(ans,(b[num].r-b[num].l+1)*(b[num].r-b[num].l)/2);                printf("%lld/%lld\n",ans/yue,(b[num].r-b[num].l+1)*(b[num].r-b[num].l)/2/yue);        }        return 0;}P2709 小B的询问

套路都差不多，依旧设 \(num_x\) 表示在当前区间中 \(x\) 出现了多少次，我们要看 \(num_x\) 变成 \(num_x+1\) 后会对答案造成什么影响，发现会让答案加上 \((num_x+1)^2-num_x^2 = num_x^2+2num_x+1-num_x^2 = 2num_x+1\)，然后删除也是一样的推法，最后套莫队板子就行了。
十年 OI 一场空，不开 long long 见祖宗！
代码：
#include<bits/stdc++.h>using namespace std;#define int long long const int N = 5e4+5;struct node{        int l;        int r;        int id;}b[N];int a[N];int tong[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x){        sum+=2*tong[a[x]]+1;        tong[a[x]]++;}void del(int x){        tong[a[x]]--;        sum-=2*tong[a[x]]+1;}int ans[N];signed main(){        int n,_,__;        scanf("%lld %lld %lld",&n,&_,&__);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%lld",&a);        }        for(int i = 1;i<=_;i++)        {                scanf("%lld %lld",&b.l,&b.r);                b.id = i;        }        sort(b+1,b+_+1,cmp);        for(int i = 1,l = 1,r = 0;i<=_;i++)        {                while(l>b.l)                {                        add(--l);                }                while(r<b.r)                {                        add(++r);                }                while(l<b.l)                {                        del(l++);                }                while(r>b.r)                {                        del(r--);                }                ans[b.id] = sum;        }        for(int i = 1;i<=_;i++)        {                printf("%lld\n",ans);        }        return 0;}CF86D Powerful array

你会发现跟上一题没啥区别，就多了个 $ \times i$，那也一样啊。
十年 OI 一场空，不开 long long 见祖宗！
代码：
#include<bits/stdc++.h>using namespace std;#define int long long const int N = 5e4+5;struct node{        int l;        int r;        int id;}b[N];int a[N];int tong[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x){        sum+=2*tong[a[x]]+1;        tong[a[x]]++;}void del(int x){        tong[a[x]]--;        sum-=2*tong[a[x]]+1;}int ans[N];signed main(){        int n,_,__;        scanf("%lld %lld %lld",&n,&_,&__);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%lld",&a);        }        for(int i = 1;i<=_;i++)        {                scanf("%lld %lld",&b.l,&b.r);                b.id = i;        }        sort(b+1,b+_+1,cmp);        for(int i = 1,l = 1,r = 0;i<=_;i++)        {                while(l>b.l)                {                        add(--l);                }                while(r<b.r)                {                        add(++r);                }                while(l<b.l)                {                        del(l++);                }                while(r>b.r)                {                        del(r--);                }                ans[b.id] = sum;        }        for(int i = 1;i<=_;i++)        {                printf("%lld\n",ans);        }        return 0;}CF617E XOR and Favorite Number

终于有稍微难那么一点的啦！首先你要知道异或的一个基础性质：如果 \(a \oplus b = c\)，那么 \(b \oplus c = a\)，还有 \(x \oplus x = 0\)。根据这两个性质我们就可以发现我们可以将读入进来的原数组求个前缀异或，然后正常套莫队就行了。
有几个注意点：

• 由于 \(\oplus_{i = l}^r a_i = sum_r \oplus sum_{l-1}\)，所以我们读入的区间需要将左端点减 \(1\)。
  
• 十年 OI 一场空，不开 long long 见祖宗！
  
• 由于是异或，我们一开始需要初始化 \(num_0 = 1\)，因为我们存在一个 \(sum_0 = 0\)。
  

代码：
#include<bits/stdc++.h>using namespace std;#define int long long const int N = 1e6+5;struct node{        int l;        int r;        int id;}b[N];int a[N];int tong[N];int len;int k;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x){        sum+=tong[a[x]^k];        tong[a[x]]++;}void del(int x){        tong[a[x]]--;        sum-=tong[a[x]^k];}int ans[N];signed main(){        int n,_;        scanf("%lld %lld %lld",&n,&_,&k);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%lld",&a);                a^=a[i-1];        }        for(int i = 1;i<=_;i++)        {                scanf("%lld %lld",&b.l,&b.r);                b.l--;                b.id = i;        }        sort(b+1,b+_+1,cmp);        tong[0] = 1;        for(int i = 1,l = 0,r = 0;i<=_;i++)        {                while(l>b.l)                {                        add(--l);                }                while(r<b.r)                {                        add(++r);                }                while(l<b.l)                {                        del(l++);                }                while(r>b.r)                {                        del(r--);                }                ans[b.id] = sum;        }        for(int i = 1;i<=_;i++)        {                printf("%lld\n",ans);        }        return 0;}P5268 [SNOI2017] 一个简单的询问

目前最难的一道题，首先题目给了两个区间，我们知道莫队是只能处理一个区间的，但是我们可以将这两个区间拆开：

\[\sum_{x = 0}^\infty \operatorname{get}(l_1,r_1,x) \times \operatorname{get}(l_2,r_2,x)\]


\[\sum_{x = 0}^\infty (\operatorname{get}(1,r_1,x)-\operatorname{get}(1,l_1-1,x)) \times (\operatorname{get}(1,r_2,x)-\operatorname{get}(1,l_2-1,x))\]


\[\sum_{x = 0}^\infty \operatorname{get}(1,r_1,x) \times \operatorname{get}(1,r_2,x)-\operatorname{get}(1,r_1,x) \times \operatorname{get}(1,l_2-1,x)-\operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,r_2,x)+\operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,l_2-1,x)\]

然后设：

\[q_1 = \operatorname{get}(1,r_1,x) \times \operatorname{get}(1,r_2,x)\]


\[q_2 = \operatorname{get}(1,r_1,x) \times \operatorname{get}(1,l_2-1,x)\]


\[q_3 = \operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,r_2,x)\]


\[q_4 = \operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,l_2-1,x)\]

那么答案就是：

\[\sum_{x = 0}^\infty q_1-q_2-q_3+q_4\]

我们只需要将询问强行拆成这四种，每种只有两个数，于是就可以莫队了！不过你在处理的时候要注意：看似你是在使用 \(\operatorname{add}\) 函数，你需要判断你是左端点扩充还是右端点扩充，如果你是左端点扩充，那么其实相当于你在做删除操作，反之则正常，\(\operatorname{del}\) 函数也是一样。
十年 OI 一场空，不开 long long 见祖宗！
代码：
#include<bits/stdc++.h>using namespace std;#define int long long const int N = 2e5+5;struct node{        int l;        int r;        int id;//询问编号        int idd;//在这个询问的几个要处理的变量 }b[N];int a[N];int tong1[N];int tong2[N];int len;int cmp(node x,node y){        int idx = (x.l-1)/len+1,idy = (y.l-1)/len+1;        return idx == idy?x.r<y.r:idx<idy;}int sum;void add(int x,int opt)//opt用来记录你是左端点扩充还是右端点扩充{        if(!opt)        {                sum-=tong2[a[x+1]];                tong1[a[x+1]]--;        }        else        {                sum+=tong1[a[x]];                tong2[a[x]]++;        }}void del(int x,int opt)//opt用来记录你是左端点扩充还是右端点扩充{        if(!opt)        {                sum+=tong2[a[x+1]];                tong1[a[x+1]]++;        }        else        {                sum-=tong1[a[x]];                tong2[a[x]]--;        }}int ans[4][N];signed main(){        int n,_;        scanf("%lld",&n);        len = sqrt(n);        for(int i = 1;i<=n;i++)        {                scanf("%lld",&a);        }        scanf("%lld",&_);        int cnt = 0;        for(int i = 1;i<=_;i++)        {                int l1,r1,l2,r2;                scanf("%lld %lld %lld %lld",&l1,&r1,&l2,&r2);                b[++cnt] = {r1,r2,i,0};                b[++cnt] = {r1,l2-1,i,1};                b[++cnt] = {l1-1,r2,i,2};                b[++cnt] = {l1-1,l2-1,i,3};        }        sort(b+1,b+cnt+1,cmp);        for(int i = 1,l = 1,r = 0;i<=cnt;i++)        {                while(l>b.l)                {                        add(--l,0);                }                while(r<b.r)                {                        add(++r,1);                }                while(l<b.l)                {                        del(l++,0);                }                while(r>b.r)                {                        del(r--,1);                }                ans[b.idd][b.id] = sum;        }        for(int i = 1;i<=_;i++)        {                printf("%lld\n",ans[0]-ans[1]-ans[2]+ans[3]);        }        return 0;}本人之后还会在这里放上其它习题，敬请期待！
本人预估不久后（明天早上/今天晚上/下个星期）会更新带修莫队，敬请期待！