91 分 WA #4 MnZn 求助
查看原帖
91 分 WA #4 MnZn 求助
542905
WannaYellow楼主2022/7/23 09:05
#include<iostream>
#define int long long
using namespace std;
int a[100005],b[100005],n,m;
struct SegTree{
	#define mid ((l+r)>>1)
	int nod[100005<<2],t[100005<<2];
	inline int ls(int x){return x<<1;}
	inline int rs(int x){return x<<1|1;}
	inline void update(int x){nod[x]=nod[ls(x)]+nod[rs(x)];}
	void build(int x,int l,int r)	{
		if(l==r)nod[x]=b[l];
		else{
			build(ls(x),l,mid);
			build(rs(x),mid+1,r);
			update(x);
		}
	}
	void add(int x,int l,int r,int k){
		t[x]+=k;
		nod[x]+=(r-l+1)*k;
	} 
	void push_down(int x,int l,int r){
		if(t[x]){
			add(ls(x),l,mid,t[x]);
			add(rs(x),mid+1,r,t[x]);
			t[x]=0;
		}
	}
	void modify(int x,int l,int r,int ml,int mr,int k){
		if(ml<=l&&r<=mr)add(x,l,r,k);
		else{
			push_down(x,l,r);
			if(ml<=mid)modify(ls(x),l,mid,ml,mr,k);
			if(mr>mid)modify(rs(x),mid+1,r,ml,mr,k);
			update(x);
		}
	}
	int query(int x,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr)return nod[x];
		push_down(x,l,r);
		int re=0;
		if(ql<=mid)re+=query(ls(x),l,mid,ql,qr);
		if(qr>mid)re+=query(rs(x),mid+1,r,ql,qr);
		return re;
	}
	#undef mid
}T;
void M(int l,int r,int K,int D){
	T.modify(1,1,n,l,l,K);
	T.modify(1,1,n,l+1,r,D);
	if(r+1>n)return;
	T.modify(1,1,n,r+1,r+1,-(K+(r-l)*D));
}
int Q(int pos){
	return T.query(1,1,n,1,pos);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i]-a[i-1];
	}
	T.build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,k,d;
			cin>>l>>r>>k>>d;
			M(l,r,k,d);
		}else if(opt==2){
			int pos;
			cin>>pos;
			cout<<Q(pos)<<"\n";
		}
	}
	return 0;
}

记录如此

2022/7/23 09:05
加载中...