线段树9pts求调
查看原帖
线段树9pts求调
752619
Sorato_楼主2024/3/7 21:36

rt,只过了第一个点

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0;
	short f=1;
	char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
struct seg
{
	int l,r,dat,add;
	#define mid (t[p].l+t[p].r>>1)
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define len(p)	(t[p].r-t[p].l+1)
}t[2000000];
int num[500010];
inline void upd(int p)
{
	t[p].dat=t[ls].dat+t[rs].dat;
}
inline void spread(int p)
{
	if(t[p].add)
		t[ls].add+=t[p].add,
		t[rs].add+=t[p].add,
		t[ls].dat+=t[p].add*len(ls),
		t[rs].dat+=t[p].add*len(rs),
		t[p].add=0;
}
void build(int p,int l,int r)
{
	t[p].l=l;t[p].r=r;
	if(l==r)
	{
		t[p].dat=num[l]-num[l-1];
		return;
	}
	build(ls,l,mid);
	build(rs,-~mid,r);
	upd(p);
}
void change1(int p,int pos,int d)
{
	if(t[p].l==t[p].r)
	{
		t[p].dat+=d;
		return;
	}
	spread(p);
	if(pos<=mid)	change1(ls,pos,d);
	if(mid<pos)	change1(rs,pos,d);
	upd(p);
}
void change2(int p,int l,int r,int d)
{
	if(t[p].l>=l&&t[p].r<=r)
	{
		t[p].dat+=d*len(p);t[p].add+=d;
		return;
	}
	spread(p);
	if(l<=mid)	change2(ls,l,mid,d);
	if(mid<r)	change2(rs,-~mid,r,d);
	upd(p);
}
int query(int p,int l,int r)
{
	if(t[p].l>=l&&t[p].r<=r)	return t[p].dat;
	spread(p);
	int res=0;
	if(mid>=l)	res+=query(ls,l,r);
	if(mid<r)	res+=query(rs,l,r);
	upd(p);
	return res;
}
int n,m,a,b,c,d;
signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i=-~i)	num[i]=read();
	build(1,1,n);
	for(int i=1;i<=m;i=-~i)
	{
		if(read()==1)
		{
			a=read();b=read();c=read();d=read();
			change1(1,a,c);
			if(b<n)	change1(1,-~b,-c-(b-a)*d);
			if(a<b)	change2(1,-~a,b,d);
		}
		else
			printf("%lld\n",query(1,1,read()));
	}
	return 0;
}
2024/3/7 21:36
加载中...