玄关求调!分块样例已过全WA
查看原帖
玄关求调!分块样例已过全WA
779823
liuxinying886楼主2025/2/6 10:54
#include<bits/stdc++.h>
#define int long long
using namespace std;
int pos[500100],n,m,a[200100],vis[200100],visn,tag[200100],sumn[200100];
void put(int l,int r,int x){ 
	for(int i=l;i<=min(r,pos[l]*visn);i++){
	    a[i]+=x;
		sumn[pos[l]]+=a[i]; 
	} 
	if(pos[l]!=pos[r]){ 
		for(int i=(pos[r]-1)*visn+1;i<=r;i++){
			a[i]+=x;
			sumn[pos[r]]+=a[i];
		}
	}
	for(int i=pos[l]+1;i<=pos[r]-1;i++){ 
		tag[i]+=x; 
		sumn[i]+=visn*x;
	}
}
int find(int l,int r){ 
	int sum=0;
	for(int i=l;i<=min(r,pos[l]*visn);i++){
		sum+=a[i]+tag[pos[l]];
	} 
	if(pos[l]!=pos[r]){
		for(int i=(pos[r]-1)*visn+1;i<=r;i++){
			sum+=a[i]+tag[pos[r]];
		} 
	}
	for(int i=pos[l]+1;i<pos[r];i++){
		sum+=sumn[i];
	}  
	return sum;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	visn=sqrt(n);  
	for(int i=1;i<=n;i++)pos[i]=(i-1)/visn+1; 
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sumn[pos[i]]+=a[i];
	}
	while(m--){
		int num;
		cin>>num;
		if(num==1){
			int l,r,x;
			cin>>l>>r>>x;
			put(l,r,x);
		}
		if(num==2){
			int x;
			cin>>x;
			a[1]+=x;
			sumn[pos[1]]+=x;
		}
		if(num==3){
			int x;
			cin>>x;
			a[1]-=x;
			sumn[pos[1]]-=x;
		}
		if(num==4){
			int l,r;
			cin>>l>>r;
			cout<<find(l,r)<<endl;
		}
		if(num==5){
			cout<<a[1]+tag[pos[1]]<<endl;
		}
	}
	return 0;
}  

提前感谢大佬帮助!

2025/2/6 10:54
加载中...