莫队

先说分块

牛
分块就是将一个序列，分成若干个区间（一般一个区间取sqrt(n)）
于是在进行选择分块策略时,主要解决以下几个问题:
1.针对不完整块如何进行处理?
2.完整的块如何进行处理?
3.需要对每个块维护哪些信息?如何进行预处理?
4.如何合并答案?
例子：给出一个长为 n的数列，以及n 个操作，操作涉及区间加法，单点查值。
有一个数据记整块的加值，如果是整个区间，直接改加值，不完整的区间单独改每一个数的值.

接下来说莫队

牛
例：一个区间多次询问，问一个区间内有多少种数，暴力的解法就是，一个左指针，一个右指针，询问一个一个查，左边不行就推左边，右边不行就推用边，直到和询问区间重合，但直接这样查时间复杂度很高，这是后就可以用莫队，利用分块的思想，将区间分成根号n个块，按照左端点所在的块排序，如果相等就按照右端点的位置排序.

时间复杂度为n乘根号n

一些优化

1.另外吸氧，和快读对莫队优化很大

2.还有把这个

int cmp(query a, query b) {
   
    return belong[a.l] == belong[b.l] ? a.r < b.r : belong[a.l] < belong[b.l];
}

改成这个

int cmp(query a, query b) {
   
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

也就是说，对于左端点在同一奇数块的区间，右端点按升序排列，反之降序。这个东西也是看着没用，但实际效果显著。
它的主要原理便是右指针跳完奇数块往回跳时在同一个方向能顺路把偶数块跳完，然后跳完这个偶数块又能顺带把下一个奇数块跳完。理论上主算法运行时间减半，实际情况有所偏差

3.把这两个

void add(int pos) {
   
    if(!cnt[aa[pos]]) ++now;
    ++cnt[aa[pos]];
}
void del(int pos) {
   
    --cnt[aa[pos]];
    if(!cnt[aa[pos]]) --now;
}

while(l < ql) del(l++);
while(l > ql) add(--l);
while(r < qr) add(++r);
while(r > qr) del(r--);

合并成这个

while(l < ql) now -= !--cnt[aa[l++]];
while(l > ql) now += !cnt[aa[--l]]++;
while(r < qr) now += !cnt[aa[++r]]++;
while(r > qr) now -= !--cnt[aa[r--]];

也能优化很多，但实际上不是很好写，不建议不熟练的情况下这样写

接下来放一下例题代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 1010000
#define maxb 1010
int aa[maxn],cnt[maxn],belong[maxn];
int n,m,size,bnum,now,ans[maxn];
struct query{
   
    int l,r,id;
} q[maxn];
int cmp(query a,query b){
   
    return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l] & 1)?a.r<b.r:a.r>b.r);
}
#define isdigit(x) ((x)>='0'&&(x)<='9')
int read(){
   
    int res=0;
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) res=(res << 1)+(res << 3)+c-48, c=getchar();
    return res;
}
void printi(int x){
   
    if(x/10) printi(x/10);
    putchar(x%10+'0');
}
int main(){
   
    scanf("%d", &n);
    size=sqrt(n);
    bnum=ceil((double)n / size);//大于的第一个整数 
    for(int i = 1;i<=bnum;++i) 
        for(int j=(i-1)*size+1;j<=i*size;++j){
   
            belong[j]=i;
        }
    for(int i=1;i<=n;++i) aa[i]=read(); 
    m=read();
    for(int 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=1,r=0;
    for(int i=1;i<=m;++i) {
   
        int ql=q[i].l,qr=q[i].r;
        while(l<ql) now-=!--cnt[aa[l++]];
        while(l>ql) now+=!cnt[aa[--l]]++;
        while(r<qr) now+=!cnt[aa[++r]]++;
        while(r>qr) now-=!--cnt[aa[r--]];
        ans[q[i].id] = now;
    }
    for(int i=1;i<=m;++i) printi(ans[i]), putchar('\n');
    return 0;
}