分块求助qwq
查看原帖
分块求助qwq
455558
Imiya楼主2022/1/24 17:31

第七个点wrong answer 8032nd numbers differ - expected: '0', found: '316' 调了一天了QAQ

#include<iostream>
#include<cmath>
using namespace std;
inline int read(){
	int res=0,in=getchar();
	while(in<'0'||in>'9')in=getchar();
	while(in>='0'&&in<='9')res=(res<<1)+(res<<3)+(in^48),in=getchar();
	return res;
}
const int N=100100,S=333;
int n,m,k,siz,bel[N],nam[S][N],col[N*S],fa[N*S],laz[S],cnt[N*S],mx[S];
int find(int id){return fa[id]=(fa[id]==id?id:find(fa[id]));}
inline void insert(int id,int i){
	cnt[id]++;
	fa[i]=id;
}
inline void erase(int i){
	cnt[find(i)]--;
	fa[i]=0;
}
inline int getName(int blk,int x){
	if(!nam[blk][x])nam[blk][x]=++k,col[k]=x,fa[k]=k;
	return nam[blk][x];
}
inline int move(int&fro,int&to){
	if(to)fa[fro]=to,cnt[to]+=cnt[fro],cnt[fro]=0;
	else to=fro;
}
void init(){
	cin>>n>>m;
	siz=(int)sqrt(n);
	k=n;
	for(int i=1;i<=n;i++){
		int x=read();
		bel[i]=(i-1)/siz+1;
		mx[bel[i]]=max(mx[bel[i]],x);
		insert(getName(bel[i],x),i);
	}
}
void update(int l,int r,int x){
	for(int i=l;i<=min(bel[l]*siz,r);i++)
		if(col[find(i)]-laz[bel[i]]>x){
			int num=col[find(i)];
			erase(i);
			insert(getName(bel[i],num-x),i);
		}
	if(bel[l]!=bel[r])
	for(int i=bel[r]*siz-siz+1;i<=r;i++)
		if(col[find(i)]-laz[bel[i]]>x){
			int num=col[find(i)];
			erase(i);
			insert(getName(bel[i],num-x),i);
		}
	for(int i=bel[l]+1;i<bel[r];i++)
		if(mx[i]-laz[i]>x){
			if(mx[i]-laz[i]<=x*2){
				for(int j=x+laz[i]+1;j<=mx[i];j++){
					move(nam[i][j],nam[i][j-x]);
					col[nam[i][j-x]]=j-x;
					nam[i][j]=0;
				}
				for(mx[i]=x+laz[i];!nam[i][mx[i]];mx[i]--);
			}
			else{
				for(int j=laz[i]+1;j<=x+laz[i];j++){
					move(nam[i][j],nam[i][j+x]);
					col[nam[i][j+x]]=j+x;
					nam[i][j]=0;
				}
				laz[i]+=x;
			}
		}
}
int get(int l,int r,int x){
	int res=0;
//	for(int i=1;i<=n;i++)cout<<col[find(i)]<<' '<<laz[bel[i]]<<"  ";cout<<endl;
//	cout<<l<<' '<<r<<' '<<x<<endl;
	for(int i=l;i<=min(r,bel[l]*siz);i++)res+=(col[find(i)]-laz[bel[i]]==x);
	if(bel[l]!=bel[r])
	for(int i=bel[r]*siz-siz+1;i<=r;i++)res+=(col[find(i)]-laz[bel[i]]==x);
	for(int i=bel[l]+1;i<bel[r];i++)res+=cnt[nam[i][x+laz[i]]];
	return res;
}
int main(){
//	freopen("E://read.txt","r",stdin);
	init();
	while(m--){
//		for(int i=1;i<=n;i++)cout<<col[find(i)]-laz[bel[i]]<<' ';cout<<endl;
		int opt=read(),l=read(),r=read(),x=read();
		if(opt==1)update(l,r,x);
		else printf("%d\n",get(l,r,x));
	}
	return 0;
}		
		
2022/1/24 17:31
加载中...