线段树+差分,全WA了,向大佬们求助
查看原帖
线段树+差分,全WA了,向大佬们求助
609243
wuyushan楼主2023/1/15 13:17
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int a[MAXN],lazy[4*MAXN];
long long t[4*MAXN];
void pushup(int k)
{
	t[k]=t[k<<1]+t[k<<1|1]; 
}
void pushdown(int k,int l,int r)
{
	if(lazy[k])
	{
		int x=lazy[k];
		int mid=(l+r)>>1;
		lazy[k<<1]+=x;
		t[k<<1]+=(mid-l+1)*x;
		lazy[k<<1|1]+=x;
		t[k<<1|1]+=(r-mid+1)*x;
		lazy[k]=0;
	}
}
int find(int L,int R,int l,int r,int k)
{
	if(L<=l&&r<=R)
	{
		int res=t[k];
		return res;
	}
	else
	{
		pushdown(k,l,r);
		int res=0;
		int mid=(l+r)>>1;
		if(L<=mid)
		{
			res+=find(L,R,l,mid,k<<1);
		}
		if(R>mid)
		{
			res+=find(L,R,mid+1,r,k<<1|1);
		}
		pushup(k);
		return res;
	}
}
void change(int L,int R,int l,int r,int k,int v)
{
	if(L<=l&&r<=R)
	{
		lazy[k]+=v;
		t[k]+=(r-l+1)*v;
	}
	else
	{
		pushdown(k,l,r);
		int mid=(l+r)>>1;
		if(L<=mid)
		{
			change(L,R,l,mid,k<<1,v);
		}
		if(R>mid)
		{
			change(L,R,mid+1,r,k<<1|1,v);
		}
		pushup(k);
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	memset(t,0,sizeof(t));
	memset(lazy,0,sizeof(lazy));
	while(m--)
	{
		int opt;
		scanf("%d",&opt);
		if(opt==1)
		{
			int l,r,K,D;
			scanf("%d%d%d%d",&l,&r,&K,&D);
			change(l,l,1,n,1,K);
			if(l+1<r)change(l+1,r,1,n,1,D);
			if(r<n)change(r+1,r+1,1,n,1,-((r-l)*D+K));
		}
		if(opt==2)
		{
			int p;
			scanf("%d",&p);
			int ans=a[p]+find(1,p,1,n,1);
			printf("%d\n",ans);
		}
	}
	return 0;
}
2023/1/15 13:17
加载中...