题解 P1972 【[SDOI2009]HH的项链】

楼下的银牌爷讲了莫队做法，那么鄙人就来说一说支持在线查询的可持久化线段树（俗称主席树）

所谓在线查询，就是不需要把询问都读进来，而是可以及时回答每一个询问。当输入数据被根据上一次查询的答案加密过后，莫队和离线操作就无用武之地了。这时候我们可以考虑转化问题。

对于每一个点，都制作一个next[i]表示在这个点之后最近的颜色相同的点，如果没有就设为n+1，记一下队头O（N）扫一遍就好了

考虑区间查询l~r之间的颜色种数，其实就是求所有满足(l<=i<=r,next[i]>r)的个数，因为如果某个点的next已近超出了这个区间的范围，就说明这个点对答案产生贡献了。

这个时候问题就已近被转化为给定一个序列，求区间l~r之间权值大于r的个数。

那么我们对于每个点都在可持久化的权值线段树中构造一条新的线段树链就好了，查询就是常规的权值线段树的查询。

对于每个点都要新建一条最多Log2 N个点的链，空间复杂度N log2 N；对于每次询问最多递归深度为Log2 N层，时间复杂度M Log2 N。

#include<cstdio>
#include<cstring>

using namespace std;
const int L=1000005;
const int N=50005;
const int LN=20;
struct node{int ls,rs,wei;};
int root[N],size;
struct Persistent_Segment_Tree{
    node v[N*LN];
    void insert(int l,int r,int last,int &p,int &num){
        (v[p=++size]=v[last]).wei++;
        if (l==r) return;
        int mid=(l+r)>>1;
        if (num<=mid) insert(l,mid,v[last].ls,v[p].ls,num);
            else insert(mid+1,r,v[last].rs,v[p].rs,num);
    }
    int ask(int l,int r,int x,int y,int &num){
        if (l==r) return v[y].wei-v[x].wei;
        int mid=(l+r)>>1;
        if (num<=mid) return ask(l,mid,v[x].ls,v[y].ls,num)+v[v[y].rs].wei-v[v[x].rs].wei;
            else return ask(mid+1,r,v[x].rs,v[y].rs,num);
    }
}Tree;
int n,m,a[N],head[L],next[N];
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++){
        if (head[a[i]]) next[head[a[i]]]=i;
        head[a[i]]=i;
    }
    for (int i=1;i<=n;i++) if (!next[i]) next[i]=n+1;
    for (int i=1;i<=n;i++) Tree.insert(1,n+1,root[i-1],root[i],next[i]);
    scanf("%d",&m);
    for (int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);int t;
        printf("%d\n",Tree.ask(1,n+1,root[x-1],root[y],t=y+1));
    }
}