传送门:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2453
一句话,区间不重复元素个数,如果颜色少的话可以状压,颜色多的话维护每种颜色的pre值,询问[l,r]也就是询问区间中<l的pre个数
Code:
#include<bits/stdc++.h> #define rnd() ((rand()<<16)|rand()) using namespace std; const int maxn=1e5+10; map<int,int>M,mp; set<int>S[maxn<<1]; int pre[maxn],nxt[maxn],n,m,a[maxn]; struct Treap{ struct node; node *root,*Null; struct node{ int val,key,size,s; node *c[2]; void set(int _val,node *C){ val=_val;key=rnd();c[0]=c[1]=C; size=s=1; } node *rz(){ size=c[0]->size+c[1]->size+s; return this; } }; Treap(){ Null=new node(); Null->set(INT_MIN,Null);Null->key=INT_MAX; Null->size=Null->s=0; root=Null; } void rot(node *&t,bool d){ node *p=t->c[d];t->c[d]=p->c[!d]; p->c[!d]=t;t->rz();p->rz();t=p; } void _insert(node *&t,int x){ if(t==Null){ t=new node(); t->set(x,Null); return; }if(t->val==x){ t->size++;t->s++;return; } _insert(t->c[x>t->val],x); if(t->c[x>t->val]->key<t->key) rot(t,x>t->val);else t->rz(); } void _del(node *&t,int x){ if(t==Null)return; if(t->val==x){ if(t->s>1){ t->size--; t->s--; return; } bool d=t->c[0]->key>t->c[1]->key; if(t->c[d]==Null){ delete t; t=Null; return; }rot(t,d); _del(t->c[!d],x); }else _del(t->c[x>t->val],x); t->rz(); } int _rank(node *t,int x){ if(t==Null)return 0; int r=t->c[0]->size; if(t->val>x)return _rank(t->c[0],x); if(t->val==x)return r; if(t->val<x)return r+t->s+_rank(t->c[1],x); } int size(){return root->size;} void insert(int x){return _insert(root,x);} void del(int x){return _del(root,x);} int rank(int x){return _rank(root,x);} }; struct seg_tree{ Treap t[maxn<<2]; #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define L i<<1 #define R i<<1|1 void build(int i,int l,int r){ for(int o=l;o<=r;o++) t[i].insert(pre[o]); if(l==r)return; int mid=(l+r)>>1; build(lson);build(rson); } void Change(int i,int l,int r,int pos,int val,int x){ t[i].del(val); t[i].insert(x); if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)Change(lson,pos,val,x); else Change(rson,pos,val,x); } int Query(int i,int l,int r,int l0,int r0){ if(l0<=l&&r0>=r){ int deb=t[i].rank(l0); return deb; } int mid=(l+r)>>1,ans=0; if(l0<=mid)ans+=Query(lson,l0,r0); if(r0>mid)ans+=Query(rson,l0,r0); return ans; } #undef R }T; int tot=0; void Q(int l,int r){ printf("%d\n",T.Query(1,1,n,l,r)); } void R(int pos,int val){ if(!mp[val])mp[val]=++tot,S[tot].insert(0); int x=mp[val],y=mp[a[pos]]; a[pos]=val; set<int>::iterator it1,it2; it1=--S[y].lower_bound(pos); it2=S[y].upper_bound(pos); if(it2!=S[y].end()){ T.Change(1,1,n,*it2,pre[*it2],*it1); pre[*it2]=*it1; } S[y].erase(pos); S[x].insert(pos); it1=--S[x].lower_bound(pos); it2=S[x].upper_bound(pos); T.Change(1,1,n,pos,pre[pos],*it1); pre[pos]=*it1; if(it2!=S[x].end()){ T.Change(1,1,n,*it2,pre[*it2],pos); pre[*it2]=pos; } } int main(){ srand(10086); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++){ if(!mp[a[i]])mp[a[i]]=++tot,S[tot].insert(0); pre[i]=M[a[i]]; M[a[i]]=i; S[mp[a[i]]].insert(i); }M.clear(); T.build(1,1,n); while(m--){ char op=getchar(); while(op!='Q'&&op!='R')op=getchar(); int l,r;scanf("%d%d",&l,&r); if(op=='Q'){ Q(l,r); }else{ R(l,r); } } return 0; }