萌新刚学OI,线段树求助!
查看原帖
萌新刚学OI,线段树求助!
342090
Lips楼主2020/8/11 09:59
#include<cstdio>
using namespace std;
const int MAXN=110;
int n,m,a[MAXN],tree[MAXN],tag[MAXN],ans;
inline int lc(int p){return p<<1;}
inline int rc(int p){return p<<1|1;}
void push_up(int u)
{
	tree[u]=tree[lc(u)]+tree[rc(u)];
}
void lazy_tag(int u,int l,int r,int k)
{
	tag[u]+=k;
	tree[u]+=k*(r-l+1);
}
void push_down(int u,int l,int r)
{
	int mid=(l+r)>>1;
	lazy_tag(lc(u),l,mid,tag[u]);
	lazy_tag(rc(u),mid+1,r,tag[u]);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		tree[u]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lc(u),l,mid);
	build(rc(u),mid+1,r);
	push_up(u);
}
int query(int u,int l,int r,int ln,int rn)
{
	int t=0;
	if(ln<=l&&r<=rn) return tree[u];
	push_down(u,l,r);
	int mid=(l+r)>>1;
	if(ln<=mid) t+=query(lc(u),l,mid,ln,rn);
	if(rn>mid) t+=query(rc(u),mid+1,r,ln,rn);
	return t;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int now=query(1,1,n,x,y);
		if(now>0) ans+=now;
	}
	printf("%d\n",ans);
	return 0;
}
2020/8/11 09:59
加载中...