Description
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一
段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一
个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只
好求助睿智的你，来解决这个问题。
Input
第一行：一个整数N，表示项链的长度。
第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。
第三行：一个整数M，表示HH询问的个数。
接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
N ≤ 50000，M ≤ 200000。
Output
M行，每行一个整数，依次表示询问对应的答案。
Solution
离线操作。。。
根据题意见一颗可持久化区间线段树
记录一下每种颜色上一次出现时的位置，更新对答案的贡献
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,cnt,tot,typ; int shell[50005]; int last[1000005]; int rt[50005]; struct node{ int ls; int rs; int num; }tr[5000005]; /*void build(int &o,int l,int r){ if(!o)o=++tot; if(l==r){ tr[o].num=0; return; } int mid=(l+r)>>1; build(tr[o].ls,l,mid); build(tr[o].rs,mid+1,r); }*/ void insert(int &o,int la,int l,int r,int p,int val){ o=++tot; if(l==r){ tr[o].num=tr[la].num+val; return; } tr[o].ls=tr[la].ls; tr[o].rs=tr[la].rs; int mid=(l+r)>>1; if(p>mid)insert(tr[o].rs,tr[la].rs,mid+1,r,p,val); else insert(tr[o].ls,tr[la].ls,l,mid,p,val); tr[o].num=tr[tr[o].ls].num+tr[tr[o].rs].num; } int query(int o,int l,int r,int ql,int qr){ if(l>qr||r<ql)return 0; if(ql<=l&&qr>=r){ return tr[o].num; } int mid=(l+r)>>1; return query(tr[o].ls,l,mid,ql,qr)+query(tr[o].rs,mid+1,r,ql,qr); } int main(){ scanf("%d",&n); //build(rt[0],1,n); for(int i=1;i<=n;i++){ scanf("%d",&shell[i]); insert(rt[i],rt[i-1],1,n,i,1); if(last[shell[i]]){ int tmp=rt[i]; rt[i]=0; insert(rt[i],tmp,1,n,last[shell[i]],-1); } last[shell[i]]=i; } scanf("%d",&m); for(int i=1;i<=m;i++){ int l,r; scanf("%d%d",&l,&r); printf("%d ",query(rt[r],1,n,l,r)); } return 0; }