莫队算法

BZOJ1878HH的项链(莫队算法)

莫队算法详解

莫队算法的模板题，洛谷上面的数据太强，主席树过了，莫队被卡掉了，BZOJ上面可以用莫队过。 莫队的思想就是加速了暴力的过程，分成了$\sqrt N$个块。排序的时候如果在同一个块里面就按照r从小到大排序，不在同一个块里面就按照l从小到大排序 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],cnt[N];
int tim,ans[N];
int curl=1,curr=0,res=0;
inline int read()
{
    char ch=getchar();
    int x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
inline void add(int pos)
{
    cnt[a[pos]]++;
    if(cnt[a[pos]]==1)
        res++;
}
inline void remove(int pos)
{
    cnt[a[pos]]--;
    if(cnt[a[pos]]==0)
        res--;
}
struct query
{
    int l,r,id;
} e[N];
bool cmp(query x,query y)
{
    if(x.l/tim==y.l/tim)//在同一个块
        return x.r<y.r;
    else
        return x.l<y.l;
}
int main()
{
    int n,m;
    n=read();
    for(int i=1; i<=n; i++)
        a[i]=read();
    m=read();
    tim=sqrt(m);
    for(int i=1; i<=m; i++)
    {
        e[i].l=read();
        e[i].r=read();
        e[i].id=i;
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1; i<=m; i++)
    {
        int l=e[i].l,r=e[i].r;
        while(curl<l) remove(curl++);
        while(curl>l) add(--curl);
        while(curr<r) add(++curr);
        while(curr>r) remove(curr--);
        ans[e[i].id]=res;
    }
    for(int i=1; i<=m; i++)
        printf("%d\n",ans[i]);
    return 0;
}
/*
10
1 2 3 1 1 2 1 2 3 1
1
1 2
*/