9WA求调
查看原帖
9WA求调
1264576
2010zhuanghaojun楼主2024/12/27 20:29
#include <bits/stdc++.h>
#define int long long 
using namespace std;
struct str{
	int l,r,v,k,d;
}tr[400005];
int a[100005];
void pushup(int p) {
	tr[p].v=tr[p<<1].v+tr[p<<1|1].v;
}
void pushdown(int p) {
	int mid=(tr[p].l+tr[p].r)>>1;
	tr[p<<1].v+=(mid-tr[p].l+1)*tr[p].k+(mid-tr[p].l+1)*(mid-tr[p].l)*tr[p].d/2;
	tr[p<<1].k+=tr[p].k;
	tr[p<<1].d+=tr[p].d;
	int rk=tr[p].k+(mid-tr[p].l+1)*tr[p].d;
	int rlen=tr[p].r-mid;
	tr[p<<1|1].v+=(tr[p].r-mid)*rk+rlen*(rlen-1)*tr[p].d/2;
	tr[p<<1|1].k+=rk;
	tr[p<<1|1].d+=tr[p].d;
	tr[p].k=0;
	tr[p].d=0;	
}
void build(int p,int x,int y) {
	tr[p].l=x;
	tr[p].r=y;
	if(x==y){
		tr[p].v=a[x];
		return;
	}
	int mid=(x+y)>>1;
	build(p<<1,x,mid);
	build(p<<1|1,mid+1,y);
	pushup(p); 
}
void update(int p,int x,int y,int k,int d) {
	if(x<=tr[p].l&&tr[p].r<=y) {
		tr[p].v+=(tr[p].r-tr[p].l+1)*k+(tr[p].r-tr[p].l+1)*(tr[p].r-tr[p].l)*d/2;
		tr[p].k+=k;
		tr[p].d+=d;
		return;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid){
		update(p<<1,x,y,k,d);
	} 
	if(y>mid){
		update(p<<1|1,x,y,k+(mid-x+1)*d,d);
	}
	pushup(p);	
}
int query(int p,int t) {
	if(tr[p].l==tr[p].r){
		return tr[p].v;
	} 
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(t<=mid){
		return query(p<<1,t);
	} 
	if(t>mid){
		return query(p<<1|1,t);
	}
}
void debug() {
	for(int i=1;i<=40;i++){
		cout<<i<<" "<<tr[i].l<<" "<<tr[i].r<<": ";
		cout<<tr[i].v<<" "<<tr[i].k<<" "<<tr[i].d<<"\n";
	}
}
signed main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0),cout.tie(0);
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	//a[754]=8
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int f;
		cin>>f;
		if(f==1){
			int x,y,k,d;
			cin>>x>>y>>k>>d;
			update(1,x,y,k,d);
			
		} 
		else{
			int t;
			cin>>t;
			long long tmp = query(1,t);
			cout<<tmp<<"\n"; 
			
		}
		//debug();
	}
}
2024/12/27 20:29
加载中...