lp4117 Ynoi2018 五彩斑斓的世界

虽然我没有玩过这个Galgame,但是就截图而言画风还是挺可爱的。
抱歉离题了。
这是一道由乃省的省选题。
大家都知道喜欢由乃的某人最喜欢的就是数据结构了。
仔细观察这道题的数据范围,我们可以想到分块。
对于每个块里面数值相同的数维护一个并查集,对于每一个并查集维护它的大小。那么我们每一次修改,如果是暴力修改就只需要改变一个元素所在的集合,如果是整块修改就将并查集合并。
查询的时候块外部分暴力更新,快内部分按块查询即可。
但是这一题的常数简直丧心病狂,毒瘤lxl简直是魔鬼。SIZE大了T,SIZE小了MLE。我卡了整整十九次,最终结合前人优秀经验,使用unsigned char成功卡了过去。
大家记住这组魔法的数字:253-410

#include<iostream>
#include<cstdio>
#include<cmath>
#define MAXNUM 410
int SIZE,NUM;
int bl[100005],lb[MAXNUM],rb[MAXNUM];
int a[100005],tgb[MAXNUM];
int val[100005],mx[100005],fa[100005];
unsigned char cnt[MAXNUM][100005],loc[MAXNUM][100005];
int n,m;
inline int fthr(int X){
	while(X^fa[X]){
		X=fa[X]=fa[fa[X]];
	}
	return X;
}
inline void uni(int X,int A,int B){
	//将X块中的A合并到B处。若B处存在则直接合并,否则将B移动到A并修改A的值。 
	loc[X][B]?fa[loc[X][A]+lb[X]-1]=loc[X][B]+lb[X]-1:(loc[X][B]=loc[X][A],val[loc[X][A]+lb[X]-1]=B);
	cnt[X][B]+=cnt[X][A],cnt[X][A]=loc[X][A]=0;
}
inline void del(int S,int X){
	//如果X比最大值的一半还要小,那么我们考虑将所有小于X的上移,并且修改标记;否则将所有大于X的下移。 
	if((X<<1)<=mx[S]-tgb[S]){
		for(int i=tgb[S]+1;i<=tgb[S]+X;++i){
			if(loc[S][i]){
				uni(S,i,i+X);
			}
		}
		tgb[S]+=X; 
	}else{
		for(int i=X+tgb[S]+1;i<=mx[S];++i){
			if(loc[S][i]){
				uni(S,i,i-X);
			}
		}
		mx[S]=std::min(mx[S],tgb[S]+X);
	}
}
inline void pshd(int X){
	for(int i=lb[X];i<=rb[X];++i){
		a[i]=val[fthr(i)];
		loc[X][a[i]]=cnt[X][a[i]]=0;
		//应当先清空再修改标记。 
		a[i]-=tgb[X];
	}
	for(int i=lb[X];i<=rb[X];++i){
		fa[i]=0;
	}
	tgb[X]=0;
}
inline void updt(int X){
	mx[X]=0;
	for(int i=lb[X];i<=rb[X];++i){
		mx[X]=std::max(mx[X],a[i]);
		loc[X][a[i]]?(fa[i]=loc[X][a[i]]+lb[X]-1):(fa[i]=i,val[i]=a[i],loc[X][a[i]]=i-lb[X]+1);
		++cnt[X][a[i]];
	}
}
inline void chng(int L,int R,int X){
	if(bl[L]^bl[R]){
		pshd(bl[L]),pshd(bl[R]);
		for(int i=L;i<=rb[bl[L]];++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		for(int i=lb[bl[R]];i<=R;++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		updt(bl[L]),updt(bl[R]);
		for(int i=bl[L]+1;i<=bl[R]-1;++i){
			del(i,X);
		}
	}else{
		pshd(bl[L]);
		for(int i=L;i<=R;++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		updt(bl[L]);
	}
}
inline int qry(int L,int R,int X){
	if(bl[L]^bl[R]){
		int rt=0;
		for(int i=L;i<=rb[bl[L]];++i){
			if(val[fthr(i)]-tgb[bl[L]]==X){
				++rt;
			}
		}
		for(int i=lb[bl[R]];i<=R;++i){
			if(val[fthr(i)]-tgb[bl[R]]==X){
				++rt;
			}
		}
		//注意这里减去的是其所在块的lzytg 
		for(int i=bl[L]+1;i<=bl[R]-1;++i){
			rt+=((X+tgb[i]<=100000)?cnt[i][X+tgb[i]]:0);
		}
		return rt;
	}else{
		int rt=0;
		for(int i=L;i<=R;++i){
			if(val[fthr(i)]-tgb[bl[L]]==X){
				++rt;
			}
		}
		return rt;
	}
}
inline void DEBUG(){
	for(int i=1;i<=n;++i){
		printf("%d/%d ",val[fthr(i)],a[i]);
	}
	puts("");
	for(int i=1;i<=NUM;++i){
		printf("[%d %d|%d|%d],",lb[i],rb[i],tgb[i],mx[i]);
	}
	puts("");
	/*
	for(int i=1;i<=100;++i){
		if(loc[2][i]){
			printf("{%d} ",i);
		}
	} 
	*/
}
void init(){
	scanf("%d%d",&n,&m);
	SIZE=253;
	NUM=std::ceil((double)n/SIZE);
	for(int i=1;i<=NUM;++i){
		lb[i]=(i-1)*SIZE+1;
		rb[i]=i*SIZE;
		for(int j=lb[i];j<=rb[i];++j){
			bl[j]=i;
		}
	}
	rb[NUM]=n;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=NUM;++i){
		updt(i);
	}
	int op,l,r,x;
	for(int i=1;i<=m;++i){
//		DEBUG();
		scanf("%d%d%d%d",&op,&l,&r,&x);
		if(op==1){
			chng(l,r,x);
		}else{
			printf("%d\n",qry(l,r,x));
		}
	}
}

int main(){
//	freopen("test.out","w",stdout);
	init();
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。