主席树的应用 若该位置的数出现过就把该版本的之前的位置-1 再把该版本的该位置+1,否则直接+1
查询的时候 有点像zkw线段树那种 - -
(哎呀..遭不住了啊..手真是贱啊..总是写错..花了一个小时debug真是菜啊TAT)
#include <cstdio> #include <cstring> #include <algorithm> #define lson st[num].ls #define rson st[num].rs using namespace std; const int MAXN = 30100; struct node { int ls,rs,cnt; }; struct { int rt[MAXN],cur,rc; node st[MAXN*20]; inline void _pushUp(int num) { st[num].cnt=st[lson].cnt+st[rson].cnt; } inline int _build(int l,int r) { int num=cur++,m=(l+r)>>1; if(l==r) { st[num].cnt=0; return num; } st[num].ls=_build(l,m); st[num].rs=_build(m+1,r); _pushUp(num); return num; } inline int _insert(int pos,int v,int l,int r,int last) { int num=cur++,m=(l+r)>>1; st[num]=st[last]; if(l==r) { st[num].cnt+=v; return num; } if(pos>m) st[num].rs=_insert(pos,v,m+1,r,st[num].rs); else st[num].ls=_insert(pos,v,l,m,st[num].ls); _pushUp(num); return num; } inline int _quire(int pos,int l,int r,int num) { if(l==r) return st[num].cnt; int m=(l+r)>>1; if(pos<=m) return st[rson].cnt+_quire(pos,l,m,st[num].ls); else return _quire(pos,m+1,r,st[num].rs); } inline void init(int n) { cur=rc=0; rt[rc++]=_build(1,n); } inline void insert(int n,int has,int pos) { if(has) { int tmp=_insert(has,-1,1,n,rt[rc-1]); rt[rc]=_insert(pos,1,1,n,tmp); } else rt[rc]=_insert(pos,1,1,n,rt[rc-1]); rc++; } inline int quire(int n,int l,int r) { return _quire(l,1,n,rt[r]); } }fst; int hl[MAXN],hs[MAXN],pos[MAXN]; int main() { //freopen("spojDquiry.in","r",stdin); int n,m; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",&hs[i]); hl[i]=hs[i]; } memset(pos,0,sizeof(pos)); sort(hl+1,hl+n+1); int nn=unique(hl+1,hl+n+1)-hl-1; fst.init(n); int p; for(int i=1;i<=n;i++) { p=lower_bound(hl+1,hl+nn+1,hs[i])-hl; fst.insert(n,pos[p],i); pos[p]=i; } scanf("%d",&m); while(m--) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",fst.quire(n,l,r)); } } return 0; }