萌新刚学OI,分块求调QwQ(T*3)
查看原帖
萌新刚学OI,分块求调QwQ(T*3)
452438
_Minecraft12345楼主2023/2/7 09:09
#include<bits/stdc++.h>
using namespace std;
const int _=5e5+10;
int n,m;
int a[_],pos[_],lazy[_],l[_],r[_];
void init(){
	int t=sqrt(n);
	for(int i=1;i<=t;i++){
		l[i]=(i-1)*t;
		r[i]=i*t;
	}
	if(r[t]<n){
		t++;
		l[t]=r[t-1]+1;
		r[t]=n;
	}
	for(int i=1;i<=t;i++){
		for(int j=l[i];j<=r[i];j++){
			pos[j]=i;
		}
	}
}
void update(int x,int y,int k){
	int p=pos[x],q=pos[y];
	if(p==q){
		for(int i=x;i<=y;i++){
			a[i]+=k;
		}return;
	}
	for(int i=p+1;i<q;i++){
		lazy[i]+=k;
	}
	for(int i=x;i<=r[p];i++){
		a[i]+=k;
	}
	for(int i=l[q];i<=y;i++){
		a[i]+=k;
	}
}
int get(int x){
	return a[x]+lazy[pos[x]];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}for(int i=1;i<=m;i++){
		int op;
		cin>>op;
		if(op==1){
			int x,y,k;
			cin>>x>>y>>k;
			update(x,y,k);
		}else{
			int k;
			cin>>k;
			cout<<get(k)<<endl;
		}
	}
	
	return 0;
}
2023/2/7 09:09
加载中...