莫队

莫对是一种将区间询问离线处理的优雅的暴力。(主要思想：分块)

普通莫队

对于形如 [l,r]的询问,莫队首先将所有询问存储下来，通过排序优化区间的转移,那么对于序列上的区间询问问题。如从[l,r]的答案可以O(1)转移到[l-1,r],[l+1,][l,r-1][l,r+1],那我们可以在\(O(n\sqrt{n})\)的时间复杂度求出所有答案。

给一个序列，m次询问，每次询问你区间[l,r][l,r]有多少种不同的颜色。\(n,m\leq 100000n,m≤100000\)

我们可以使用一个数组cnt[x],表示x出现的次数,用两个指针l,r表示当前区间,每次指针移动时,如果指向的元素在此前未出现即cnt[x]=0，那说明出现了新元素,我们的答案+1。

void add(int x){
    cnt[x]++;
    if(cnt[x]==1)ans++;
}

void del(int x){
    cnt[x]--;
    if(cnt[x]==0)ans--;
}

//获取答案：
while(l>q[i].l) add(a[--l]);
while(r<q[i].r) add(a[++r]);
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);

如果没有进行排序优化，每次挪动都都是O(1)的，每次询问我们最多要挪动n次，所以时间复杂度是O(nm)。
我们必须减少移动次数。

我们将询问存储下来，离线操作,对于每个区间我们按左端点排序，这样我们的左端点只会不断向右移动，但是左端点还是可能来回跳跃，这样复杂度最坏还是O(nm)，显然是不行的。

我们将序列分成\(\sqrt{n}\)块，以左端点所在块为第一关键字，右端点为第二关键字，这样对于每个块内的右端点是有序的，最多移动n次，有\(\sqrt{n}\)个块,所以复杂度\(O(n\sqrt{n})\)。

bool cmp(query a,query b){
return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}

但这样分块的话，如果n特别大还是可能超时的，所以我们考虑重新规定块的大小。
我们设块长度为S，那么对于任意多个在同一块内的询问，挪动的距离就是n，一共\(\frac{n}{S}Sn\)个块，移动的总次数就是\(\frac{n^2}{S}\)，移动可能跨越块，所以还要加上一个mS的复杂度，总复杂度为\(O(\frac{n^2}{S}+mS)\)，我们要让这个值尽量小，S取\(\frac{n}{\sqrt{m}}\)是最优的，此时复杂度为\(O(\frac{n^2}{\frac{n}{\sqrt{m}}}+m(\frac{n}{\sqrt{m}}))=O(n\sqrt{m})\),。

还有一种排序方法叫做奇偶性排序。

bool cmp(node a,node b){
return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;
}

指针移到右边后不用再跳回左边，而跳回左边后处理下一个块又要跳回右边，这样能减少一半操作，理论上能快一倍。

P1972 [SDOI2009] HH的项链

#include <bits/stdc++.h>

using namespace std;

int read()
{
    char x;
    while((x = getchar()) > '9' || x < '0') ;
    int u = x - '0';
    while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0';
    return u;
}
int buf[105];  
inline void write(int i) {  
    int p = 0;  
    if(i == 0) p++;  
    else while(i) {  
        buf[p++] = i % 10;  
        i /= 10;  
    }  
    for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]);  
} 

#define il inline
#define re register

int block,ans=0,cnt[1000001];
int n,m,a[500010],Ans[500010];

struct node {
    int l,r,id;
}q[500010];

il bool cmp(node a,node b){
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

il void add(int x){
    if(!cnt[a[x]])ans++;
    cnt[a[x]]++;
}

il void del(int x){
    cnt[a[x]]--;
    if(!cnt[a[x]])ans--;
}
int i;

int main(){
    n=read();
    for(i=1;i<=n;++i)a[i]=read();
    m=read();
    block=n/sqrt(m*2/3);
    for(i=1;i<=m;++i){
        q[i].l=read();
        q[i].r=read();
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=0,r=0;
    for(i=1;i<=m;++i){
        int ql=q[i].l,qr=q[i].r;
        while(l<ql)del(l++);
        while(l>ql)add(--l);
        while(r<qr)add(++r);
        while(r>qr)del(r--);
        Ans[q[i].id]=ans;
    }
    for(i=1;i<=m;++i)write(Ans[i]),printf("\n");
    return 0;
}

带修改莫队

未完待续...