分块板子 92pts 求调
  • 板块P2357 守墓人
  • 楼主SSqwq_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/8 17:20
  • 上次更新2023/11/2 14:55:25
查看原帖
分块板子 92pts 求调
639085
SSqwq_楼主2023/10/8 17:20

WA 了前两个点 QAQ

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct kuai{
	int l,r,sum,val;
}t[200001];
int cnt,n,len,q,a[200001];
int fa(int x){
	return (x-1)/len+1;
}
void add(int l,int r,int c){
	for(int i=1;i<=cnt;++i){
		if(t[i].l>=l&&t[i].r<=r){
			if(i<cnt){
				t[i].sum+=len*c;
			}
			else{
				t[i].sum+=(n%len)*c;
			}
			t[i].val+=c;
			continue;
		}
		if((t[i].l<=l&&t[i].r>=l)||(t[i].l<=r&&t[i].r>=r)){
			for(int j=t[i].l;j<=t[i].r;++j){
				if(j>=l&&j<=r){
					a[j]+=c;
					t[i].sum+=c;
				}
			}
		}
	}
}
int query(int l,int r){
	int ans=0;
	for(int i=1;i<=cnt;++i){
		if(t[i].l>=l&&t[i].r<=r){
			ans+=t[i].sum;
			continue;
		}
		if((t[i].l<=l&&t[i].r>=l)||(t[i].l<=r&&t[i].r>=r)){
			for(int j=t[i].l;j<=t[i].r;++j){
				if(j>=l&&j<=r){
					ans+=t[i].val+a[j];
				}
			}
		}
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	len=sqrt(n);
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int i=1;;++i){
		if(i*len>n)break;
		t[++cnt].l=(i-1)*len+1;
		t[cnt].r=i*len;
	}
	if(n%len!=0){
		t[++cnt].l=n-(n%len)+1;
		t[cnt].r=n;
	}
	for(int i=1;i<=n;++i){
		t[fa(i)].sum+=a[i];
	}
	while(q--){
		int opt,l,r,c;
		cin>>opt;
		if(opt==1){
			cin>>l>>r>>c;
			add(l,r,c);
		}
		if(opt==2){
			cin>>c;
			add(1,1,c);
		}
		if(opt==3){
			cin>>c;
			add(1,1,0-c);
		}
		if(opt==4){
			cin>>l>>r;
			cout<<query(l,r)<<endl;
		}
		if(opt==5){
			cout<<query(1,1)<<endl;
		}
	}
	return 0;
}
2023/10/8 17:20
加载中...