普通莫队

DQUERY - D-query

先想一下最朴素的暴力怎么写。显然可以用一个 \(cnt\) 数组记录每种元素的出现次数，然后如果这种元素是第一次出现，则增加答案，时间复杂度 \(O(nq)\)。

然后考虑如果如何用一个已经求出来答案的询问推出另外一个询问的答案。

显然我们要增加一部分数和删掉一部分数。对于删掉的数如果其出现次数为 \(2\)，则答案减一；对于增加的数如果其出现次数为 \(0\)，则答案加一。

然后莫队就是，在上面那种一个一个移动指针的情况下求答案。但是要预先知道所有询问，把所有询问离线下来，然后排序。

所以，莫队是一种离线算法。

现在，我们将长度为 \(n\) 的序列分为 \(\sqrt n\) 个块，先按左端点所在块的编号从小到大排序，如果出现两个询问的这一项相同，则按右端点的位置从小到大排序，这样的时间复杂度是 \(O(n \sqrt n)\) 的。

事实上是非常好理解的，所以直接看一下代码：

#include<bits/stdc++.h>
#define int long long
#define N 50005
#define M 200005
#define S 1000005
using namespace std;
int n,m,len,w[N],ans[M],cnt[S];
struct node{
    int id,l,r;
}q[M];
int get(int x){
    return x/len;
}
bool cmp(const node &a,const node &b){
    int i=get(a.l),j=get(b.l);
    if(i!=j)return i<j;
    return a.r<b.r;
}
void add(int x,int &res){
    if(!cnt[x])res++;
    cnt[x]++;
}
void del(int x,int &res){
    cnt[x]--;
    if(!cnt[x])res--;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    cin>>m;
    len=max(1ll,(int)sqrt(n*n/m));
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        q[i]={i,l,r};
    }
    sort(q,q+m,cmp);
    for(int i=0,j=1,k=0,res=0;k<m;k++){
        int id=q[k].id,l=q[k].l,r=q[k].r;
        while(i<r)add(w[++i],res);
        while(i>r)del(w[i--],res);
        while(j<l)del(w[j++],res);
        while(j>l)add(w[--j],res);
        ans[id]=res;
    }
    for(int i=0;i<m;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

代码是比较好理解的，不过注意四个移动指针的循环的顺序是有要求的，故不要随意更改顺序。

然后总结一下莫队的本质，就是在暴力的基础上把询问排个序，然后要求如果你知道询问 \([l,r]\) 的答案，在把 \(l\) 或 \(r\) 指针移动一格的情况下，仍然可以在 \(O(1)\) 复杂度内求出答案。

带修莫队

数颜色 / 维护队列

这里先说一下，带修莫队的块长一般使用 \(n^{\frac{2}{3}}\)。

带修莫队的差别和普通莫队事实上并不大，就是要加一个维度记录时间。

事实上，原来的四种转移方式再加上 \([l,r,t-1],[l,r,t+1]\) 两种转移方式就行了。