莫队算法

特点：

快速、离线处理（支持查询，不支持修改）、暴力处理长序列问题

核心思想：

• 双指针的移动
• 分块和排序

示例题洛谷P1972 [SDOI2009] HH的项链
ps:实际这道题用莫队会被卡，仅用于举例

#include<bits/stdc++.h>
using namespace std;

struct q
{
    int l;
    int r;
    int id;
}ql[1000001];
int n,m;int a[1000001];int ans[1000001];int belong[1000001];int cnt[1000001];int now;int res[1000001];
int cmp(q a,q b)
{
    //return belong[a.l]==belong[b.l]?a.r<b.r:belong[a.l]<belong[b.l];
    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);
}
void add(int pos)
{
    if(cnt[a[pos]]==0)++now;
    ++cnt[a[pos]];
}
void del(int pos)
{
    --cnt[a[pos]];
    if(cnt[a[pos]]==0)--now;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>ql[i].l>>ql[i].r;
        ql[i].id=i;
    }
    int size=sqrt(n);
    int 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;
    sort(ql+1,ql+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        int nl=ql[i].l;int nr=ql[i].r;
        //cout<<ql[i].l<<" "<<ql[i].r<<endl;
        //cout<<"l: "<<l<<" r: "<<r<<endl;
        while(l<nl)del(l++);
        while(l>nl)add(--l);
        while(r>nr)del(r--);
        while(r<nr)add(++r);
        res[ql[i].id]=now;
    }
    for(int i=1;i<=m;i++)
        cout<<res[i]<<endl;
    return 0;
}

实际上使用cnt数组存中间结果用的是1-1哈希映射，大概率空间浪费会挺大，而且某些数据集也不支持这种做法。

一些优化

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--]];