91pts代码求调
查看原帖
91pts代码求调
978312
Gyc_Fisher楼主2023/10/23 15:10

#4 挂了

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 100010
#define int long long
using namespace std;
int n,m;
int a[MAXN];
int b[MAXN];
struct SG{
	int l,r;
	int dat;
	int lazy;
}t[MAXN<<2];
void spread(int p){
	if(t[p].lazy){
		t[p*2].dat+=t[p].lazy*(t[p*2].r-t[p*2].l+1);
		t[p*2+1].dat+=t[p].lazy*(t[p*2+1].r-t[p*2+1].l+1);
		t[p*2].lazy+=t[p].lazy;
		t[p*2+1].lazy+=t[p].lazy;
		t[p].lazy=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;
	t[p].lazy=0;
	if(l==r){
		t[p].dat=b[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].dat=t[p*2].dat+t[p*2+1].dat;
}
void change(int p,int l,int r,int k){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].dat+=k*(t[p].r-t[p].l+1);
		t[p].lazy+=k;
		return;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(mid>=l) change(p*2,l,r,k);
	if(mid<r) change(p*2+1,l,r,k);
	t[p].dat=t[p*2].dat+t[p*2+1].dat;
}
int query(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r){
		return t[p].dat;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	int ans=0;
	if(mid>=l) ans+=query(p*2,l,r);
	if(mid<r) ans+=query(p*2+1,l,r);
	return ans;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i]-a[i-1];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt;
		scanf("%lld",&opt);
		if(opt==1){
			int l,r,k,d;
			scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
			change(1,l,l,k);
			if(r<n){
				change(1,r+1,r+1,-k);
				change(1,r+1,r+1,-(r-l)*d);
			}
			change(1,l+1,r,d);
		}
		else if(opt==2){
			int pos;
			scanf("%lld",&pos);
			printf("%lld\n",query(1,1,pos));
		}
	}
	return 0;
}
2023/10/23 15:10
加载中...