RE+WA 求调线段树
查看原帖
RE+WA 求调线段树
575994
Hisaishi_Kanade楼主2022/12/26 11:47
#include <stdio.h>
#define lc(id) (id<<1)
#define rc(id) (id<<1|1)
#define mid (l+r>>1)
const int maxn=100005;
int val[maxn];
long long tr[maxn<<2],tag[maxn<<2];
inline void push_up(int id)
{
	tr[id]=tr[lc(id)]+tr[rc(id)];
}
inline void build(int id,int l,int r)
{
	if(l==r)
	{
		tr[id]=val[l];
		return ;
	}
	build(lc(id),l,mid);
	build(rc(id),mid+1,r);
	push_up(id);
}
inline void reserve(int id,int l,int r,int k)
{
	tag[id]+=k;
	tr[id]+=(r-l+1)*k;
}
inline void push_down(int id,int l,int r)
{
	if(tag==0)
		return ;
	reserve(lc(id),l,r,tag[id]);
	reserve(rc(id),mid+1,r,tag[id]);
	tag[id]=0;
}
inline void update(int id,int ql,int qr,int l,int r,int k)
{
	if(ql<=l&&r<=qr)
	{
		tag[id]+=k;
		tr[id]+=k*(r-l+1);
		return ;
	}
	push_down(id,l,r);
	if(ql<=mid)
		update(lc(id),ql,qr,l,mid,k);
	if(mid<qr)
		update(rc(id),ql,qr,mid+1,r,k);
	push_up(id);
	return ;
}
inline long long query(int id,int ql,int qr,int l,int r)
{
	if(ql<=l&&r<=qr)
		return tr[id];
	long long ret=0;
	push_down(id,l,r);
    if(ql<=mid)
		ret+=query(lc(id),l,mid,ql,qr);
    if(qr>mid)
		ret+=query(rc(id),mid+1,r,ql,qr);
	return ret;
}
int main()
{
	int n,i,m,opt,l,r,k,d,pos;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%d",val+i);
	for(i=n;i>=1;--i)
		val[i]-=val[i-1];
	build(1,1,n);
	while(m--)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d %d %d %d",&l,&r,&k,&d);
			update(1,l,l,1,n,k);
			if(l+1<=r)
				update(1,l+1,r,1,n,d);
			if(r<n)
				update(1,r+1,r+1,1,n,-(k+1ll*d*(r-l)));
		}
		else
		{
			scanf("%d",&pos);
			printf("%lld",query(1,1,pos,1,n));
		}
	}
	return 0;
}

#1 AC,#2~#5 RE,其余 WA

2022/12/26 11:47
加载中...