【BZOJ2120】—数颜色（带修莫队）-白红宇

【BZOJ2120】—数颜色（带修莫队）

阅读量：5281 次

发布时间：2019-06-14

本文共 1443 字，大约阅读时间需要 4 分钟。

带修莫队版题

记录多记一维是第几次修改，记录一下修改之前是什么颜色就可以了

块大小不能开 $n\sqrt n$ ，那样复杂度没有变化

大概 $n23n^{\frac 2 3}$ 或者 $n34n^{\frac 3 4}$ 的时候最优

#include
    
     using namespace std;#define ll long long#define pb push_backinline int read(){
    	char ch=getchar();	int res=0,f=1;	while(!isdigit(ch)){
    if(ch=='-')f=-f;ch=getchar();}	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();	return res*f;}const int N=10005,M=1000005;int blo,plc[N],col[N],n,m;struct ask{
    	int l,r,t,idx;	friend inline bool operator <(const ask &a,const ask &b){
    		if(plc[a.l]!=plc[b.l])return plc[a.l]
     
      =l&&p<=r)del(p);	fr=col[p];	col[p]=to;	if(p>=l&&p<=r)add(p);}inline void out(int i){
    	int p=q[i].x,to=q[i].y,fr=q[i].z;	if(p>=l&&p<=r)del(p);	col[p]=fr;	if(p>=l&&p<=r)add(p);}inline void solve(){
    	l=1,r=0,t=0;	for(int i=1;i<=qt;i++){
    		while(r
      
       p[i].r)del(r--);		while(l
       
        p[i].l)add(--l);		while(t
        
         p[i].t)out(t--);		ans[p[i].idx]=now;	}}int main(){
    	n=read(),m=read();	for(int i=1;i<=n;i++)col[i]=read();	blo=sqrt(sqrt(n)),blo=blo*blo*blo;	for(int i=1;i<=n;i++)plc[i]=(i-1)/blo+1;	char op[3];	for(int i=1;i<=m;i++){
    		scanf("%s",op);		int x=read(),y=read();		if(op[0]=='Q')p[++qt]=(ask){
    x,y,tim,qt};		else q[++tim]=(upd){
    x,y,0};	}	sort(p+1,p+qt+1);	solve();	for(int i=1;i<=qt;i++)cout<
         
          <<'\n';}