题目 Sample Input 6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6
Sample Output 4 4 3 4
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
思路： 1.带修莫队裸体。 2.次数主席树+树状数组维护单点修改. 其实这也不算主席树 但用到了前缀的思想啊 我就这样叫 意思意思就好了 略略略
假如我们先不管修改。什么都不看。每一个下标 i 都存一个他的pre。这个pre就是，前面离他最近的一个颜色与他一样的下标。比如 2 4 2 3 3 4 4 2 那么相应的pre就是 0 0 1 0 4 2 6 1。 统计[ l , r ]不同数的个数 就是(r-l+1)-(这个区间有多少pre值>=l)，这个试探几个就很容易理解了。pre值>=l，说明在该区间内他前面已经有和他一样的数了，这个数就作废了。这就是静态主席树，因为涉及到区间，所以要上主席树。每次将pre插进去。统计的时候就是统计区间内大于pre的值。 带上修改：会改变3个点的前缀
c[x]=y,则以前 前缀等于x的那个数 j (c[j]=c[x]&&j>x) pre[j]就要改成pre[x]。c[x]现在变成了y,pre[x]就要改为x前面离x最近的一个颜色为y的下标k。x后面离x最近的一个颜色为y的下标o,以前o的前缀是k,现在pre[o]应为x.那这些乱七八糟的最近的什么的可以给一个vector< int >vec[N]维护。 vec[i]里面放的是颜色为i的下标。举个例子修改1的话就是 it1=vec[c[x]].lower_bound(vec[c[x]].begin(),vec[c[x]].end(),x);因为下标要大于x。 找到了x后面的一个颜色与x相同的下标，还要看是否存在 if(it1!=vec[c[x]].end());
反正就是细节很多！！！！！日他妈比 好想骂人T_T。
//Problem: 2120 Time:556 ms Memory:9508 kb #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #define foru(i,a,b) for(int i=a;i<=b;++i) #define m(a,b) memset(a,b,sizeof a) #define en '\n' using namespace std; typedef long long ll; const int N=1e5+5,M=1e5+5; template<class T>void rd(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } struct Query{int id,l,r,tim;}q[M]; struct Update{int pos,col,pre;}u[M]; int c[N],las[N],cnt[N*10]; int block,dexl,dexr,t,res,bl[N]; int ans[M]; inline int cmp(Query x,Query y){ if(bl[x.l]==bl[y.l]) return (bl[x.r]==bl[y.r])?(x.tim<y.tim):(bl[x.r]<bl[y.r]); return bl[x.l]<bl[y.l]; } void modi_time(int t,int f) { if(f==1) { c[u[t].pos]=u[t].col; if(dexl<=u[t].pos&&u[t].pos<=dexr) { if((--cnt[u[t].pre])==0) --res; if((++cnt[u[t].col])==1) ++res; } } else { c[u[t].pos]=u[t].pre; if(dexl<=u[t].pos&&u[t].pos<=dexr) { if((--cnt[u[t].col])==0) --res; if((++cnt[u[t].pre])==1) ++res; } } } void add(int x){ if((++cnt[c[x]])==1) ++res; } void del(int x){ if((--cnt[c[x]])==0) --res; } int main() { int n,m;rd(n),rd(m);block=sqrt(n); foru(i,1,n) rd(c[i]),las[i]=c[i],bl[i]=(i-1)/block+1; int qq=0,uu=0; foru(i,1,m) { char s[3];int x,y; scanf("%s%d%d",s,&x,&y); if(s[0]=='Q') q[++qq]=(Query){qq,x,y,uu}; else u[++uu]=(Update){x,y,las[x]},las[x]=y; } sort(q+1,q+qq+1,cmp); dexl=1,dexr=0,t=0,res=0; foru(i,1,m) { while(t<q[i].tim) modi_time(++t,1); while(t>q[i].tim) modi_time(t--,-1); while(dexr<q[i].r) add(++dexr); while(dexl>q[i].l) add(--dexl); while(dexr>q[i].r) del(dexr--); while(dexl<q[i].l) del(dexl++); ans[q[i].id]=res; } foru(i,1,qq) printf("%d\n",ans[i]); } //Problem: 2120 Time:728 ms Memory:48516 kb #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #include<vector> #define low(i) i&-i #define foru(i,a,b) for(int i=a;i<=b;++i) #define m(a,b) memset(a,b,sizeof a) #define en '\n' using namespace std; typedef long long ll; const int N=1e4+5,M=1e4+5,INF=0x3f3f3f3f; template<class T>void rd(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } int pre[N];//las[j]=i: a[i]=a[j]&&i<j; vector<int>vec[N*100]; vector<int>::iterator it1,it2,it3; int n; struct tree{int l,r;}t[N*300]; int sum[N*300],root[N],sz; void update(int wh,int val,int &x,int l,int r) { if(!x) x=++sz; sum[x]+=val; if(l==r) return; int mid=(l+r)>>1; if(wh<=mid) update(wh,val,t[x].l,l,mid); else update(wh,val,t[x].r,mid+1,r); sum[x]=sum[t[x].l]+sum[t[x].r]; } void modify(int i,int val) { int wh=pre[i]; if(!wh) return; while(i<=n) update(wh,val,root[i],1,n),i+=low(i); } int o1,o2,fin1[N],fin2[N]; int query(int k,int l,int r) { int ans=0; if(l==r) { foru(i,1,o1) ans-=sum[fin1[i]]; foru(i,1,o2) ans+=sum[fin2[i]]; return ans; } int mid=(l+r)>>1; if(k<=mid) { foru(i,1,o1) ans-=sum[t[fin1[i]].r],fin1[i]=t[fin1[i]].l; foru(i,1,o2) ans+=sum[t[fin2[i]].r],fin2[i]=t[fin2[i]].l; return ans+query(k,l,mid); } else { foru(i,1,o1) fin1[i]=t[fin1[i]].r; foru(i,1,o2) fin2[i]=t[fin2[i]].r; return query(k,mid+1,r); } } int getans(int k,int l,int r) { o1=o2=1;--l; while(l) fin1[++o1]=root[l],l-=low(l); while(r) fin2[++o2]=root[r],r-=low(r); int ans=query(k,1,n); return ans; } int c[N]; int main() { int m;rd(n),rd(m); foru(i,1,n) { rd(c[i]); int co=c[i],sz=vec[co].size(); if(sz) pre[i]=vec[co][sz-1]; vec[co].push_back(i); } foru(i,1,n) modify(i,1); foru(i,1,m) { char s[3];int x,y; scanf("%s%d%d",s,&x,&y); if(s[0]=='R') { if(c[x]==y) continue; int co=c[x],t1,t2; sort(vec[co].begin(),vec[co].end()); it1=upper_bound(vec[co].begin(),vec[co].end(),x); if(it1!=vec[co].end())//后面有=a[x]的数,将它的前缀改为此时的pre[x]. { modify(*it1,-1); pre[*it1]=pre[x]; modify(*it1,1); } sort(vec[y].begin(),vec[y].end()); it2=upper_bound(vec[y].begin(),vec[y].end(),x);//x后面颜色第一个=y的数. modify(x,-1);//x前面不存在颜色=y的数.也要将pre[x]删除啊 pre[x]=0; if(it2!=vec[y].begin())//x前面存在颜色=y的数. { pre[x]=*(--it2),++it2;//将x现在的前缀改成前面那第一个等于y的下标 modify(x,1); } else pre[x]=0; if(it2!=vec[y].end())//x后面颜色存在颜色=y的数.并且这是离x最近的一个 { modify(*it2,-1); pre[*it2]=x; modify(*it2,1); } vec[y].push_back(x),c[x]=y;//下行放在最后删除 放在前面删除的话 it1还有用 所以仍要++it1 假如删除之后vec[co]已经空了 it1++是会抛异常的！！ vec[co].erase(--it1);//后面没有=a[x]的数,vec[c[x]]也要删掉x啊!!! } else printf("%d\n",(y-x+1)-getans(x,x,y)); } }