这是一篇关于其他模板的文章 这些是其他模板分类的链接

离线算法

莫队算法

普通莫队算法

• Laoj P2100 sdoi2009HH的项链

int s,a[N],b[N],c[K],ans[M];

struct query{
    int i,l,r;

    bool operator <(const query x) const{
        return b[l]^b[x.l] ? l<x.l : b[l]&1 ? r<x.r : r>x.r;
    }
}q[M];

void add(int x){
    if(++c[x]==1) s++;
}

void del(int x){
    if(!--c[x]) s--;
}

int main(){
    int len=sqrt(n);
    for(int i=1; i<=n; i++) b[i]=i/len;
    for(int i=1; i<=m; i++) q[i].i=i;
    sort(q+1,q+m+1);

    int l=1, r=0;
    for(int i=1; i<=m; i++){
        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--]);
        ans[q[i].i]=s;
    }

    for(int i=1; i<=m; i++) printf("%d\n",ans[i]);
}