蒟蒻分块调不出来,道沦or性扭?
查看原帖
蒟蒻分块调不出来,道沦or性扭?
261262
WaltVBAlston楼主2021/11/4 20:12

RT,感谢@RainFestival大佬的帮助,但是还是调不出来

目前确定update_plus函数一定有问题,另外两个不太清楚,求dalao帮忙sesee,万分感谢

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int block,n,m,mod;
int tag_plus[355],tag_mul[355],sum[355],a[100005],p[100005],len[100005];
int now=0,now_block=1;
void update_mul(int x,int y,int k){
	for(int i=x;i<=y;i++){
		if(i%block==1&&i+len[p[i]]-1<=y){
			tag_mul[p[i]]*=k;
			sum[p[i]]*=k;
			tag_plus[p[i]]*=k;
			i+=len[p[i]]-1;
		}
		else{
			sum[p[i]]-=a[i];
			a[i]*=k;
			sum[p[i]]+=a[i];
		}
	}
	return;
}
void update_plus(int x,int y,int k){
	for(int i=x;i<=y;i++){
		if(i%block==1&&i+len[p[i]]-1<=y){
			sum[p[i]]+=len[p[i]]*k;
			tag_plus[p[i]]+=k;
			i+=len[p[i]]-1;
		}
		else{
			a[i]+=k;
			sum[p[i]]+=k;
		}
	}
	return;
}
int query(int x,int y){
	int res=0;
	for(int i=x;i<=y;i++){
		if(i%block==1&&i+len[p[i]]-1<=y){
			res+=sum[p[i]];
			i+=len[p[i]]-1;
		}
		else{
			res+=a[i]*tag_mul[i]+tag_plus[i];
		}
		cout<<res<<" "<<i<<" "<<p[i]<<" "<<sum[p[i]]<<endl;
	}
	return res;
}
int main(){
	cin>>n>>m>>mod;
	block=sqrt(n);
	tag_mul[1]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		now++;
		if(now>block)
			now=1,now_block++,tag_mul[now_block]=1;
		p[i]=now_block;
		sum[p[i]]+=a[i];
		len[p[i]]++;
	}
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			int k;
			cin>>k;
			update_mul(x,y,k);
		}
		else if(op==2){
			int k;
			cin>>k;
			update_plus(x,y,k);
		}
		else
			cout<<query(x,y)<<endl;
	}
	return 0;
}
2021/11/4 20:12
加载中...