线段树60分求助!!!
查看原帖
线段树60分求助!!!
207200
stars_abyss楼主2022/5/5 14:03

16-20 WA了

21 RE了

大佬帮忙看看

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[200005],t[400005],lazy[400005],opt,x,y,k;
void pushup(int k)
{
	t[k]=t[k<<1]+t[k<<1|1];
}
void build(int k,int l,int r)
{
	if(l==r) 
	{
		t[k]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void pushdown(int k,int l,int r,int mid)
{
	if(lazy[k])
	{
		lazy[k<<1]+=lazy[k];
		lazy[k<<1|1]+=lazy[k];
		t[k<<1]+=(mid-l+1)*lazy[k];
		t[k<<1|1]+=(r-mid)*lazy[k];
		lazy[k]=0;
	}
}
void update(int x,int y,int l,int r,int k,int v)
{
	if(l>=x && r<=y)
	{
		lazy[k]+=v;
		t[k]+=(r-l+1)*v;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(k,l,r,mid);
	if(x<=mid) update(x,y,l,mid,k<<1,v);
	if(y>mid) update(x,y,mid+1,r,k<<1|1,v);
	pushup(k);
}
int query(int x,int y,int l,int r,int k)
{
	if(l>=x && r<=y) return t[k];
	int res=0,mid=(l+r)>>1;
	pushdown(k,l,r,mid);
	if(x<=mid) res+=query(x,y,l,mid,k<<1);
	if(y>mid) res+=query(x,y,mid+1,r,k<<1|1);
	return res;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--)
    {
    	scanf("%lld",&opt);
    	if(opt==1)
    	{
    		scanf("%lld%lld%lld",&x,&y,&k);
    		update(x,y,1,n,1,k);
		}
		if(opt==2)
		{
			scanf("%lld",&k);
			update(1,1,1,n,1,k);
		}
		if(opt==3)
		{
			scanf("%lld",&k);
			update(1,1,1,n,1,-k);
		}
		if(opt==4)
		{
			scanf("%lld%lld",&x,&y);
			cout<<query(x,y,1,n,1)<<"\n";
		}
		if(opt==5) cout<<query(1,1,1,n,1)<<"\n";
	}
	return 0;
}
2022/5/5 14:03
加载中...