萌新求助,刚学线段树
查看原帖
萌新求助,刚学线段树
178992
Hanghang楼主2020/12/13 20:56

本弱鸡只会线段树1-P3372

这份代码加些什么就能做这道题了,万分感谢

代码如下:(线段树1-ac代码)


#include<bits/stdc++.h>
using namespace std;

const int N=100003,M=400003;
long long n,m,a[N],tree[M],tag[M];
void P(long long p)
{
	tree[p]=tree[p<<1]+tree[p<<1|1];
}
void B(long long p,long long pl,long long pr)
{
	tag[p]=0;if(pl==pr){tree[p]=a[pl];return;}
	long long mi=(pl+pr)>>1;
	B(p<<1,pl,mi);B(p<<1|1,mi+1,pr);P(p);
}
void A(long long p,long long pl,long long pr,long long d)
{
	tag[p]+=d;tree[p]+=d*(pr-pl+1);
}
void D(long long p,long long pl,long long pr)
{
	if(tag[p])
	{
		long long mi=(pl+pr)>>1;
		A(p<<1,pl,mi,tag[p]);A(p<<1|1,mi+1,pr,tag[p]);
		tag[p]=0;
	}
}
void U(long long L,long long R,long long p,long long pl,long long pr,long long d)
{
	if(L<=pl&&pr<=R)
	{
		A(p,pl,pr,d);return;
	}
	D(p,pl,pr);long long mi=(pl+pr)>>1;
	if(L<=mi)U(L,R,p<<1,pl,mi,d);
	if(R>mi)U(L,R,p<<1|1,mi+1,pr,d);
	P(p);
}
long long Q(long long L,long long R,long long p,long long pl,long long pr)
{
	if(pl>=L&&R>=pr)return tree[p];
	D(p,pl,pr);long long re=0,mi=(pl+pr)>>1;
	if(L<=mi)re+=Q(L,R,p<<1,pl,mi);
	if(R>mi)re+=Q(L,R,p<<1|1,mi+1,pr);
	return re;
}
int main()
{
    cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	B(1,1,n);
	for(int i=1;i<=m;i++)
	{
		long long q,l,r,d;cin>>q;
		if(q==1)
		{
			cin>>l>>r>>d;U(l,r,1,1,n,d);
		}
		else
		{
			cin>>l>>r;cout<<Q(l,r,1,1,n)<<endl;
		}
	}
	return 0;
}

2020/12/13 20:56
加载中...