线段树TLE求调
查看原帖
线段树TLE求调
995546
sheryang_OLE楼主2024/7/9 17:35
#include<iostream>
#define mid ((l+r)>>1)
#define ll long long
#define lc (x<<1)
#define rc ((x<<1)|1)
#define int long long
using namespace std;
struct node
{
	ll l,r,sum,add;
}tr[5*100005*4];
void pushup(int x)
{
	tr[x].sum=tr[lc].sum+tr[rc].sum;
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		tr[x].sum=0;
		return;
	}
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(x);
}
void pushdown(int x,int l,int r)
{
	int v=tr[x].add;
	tr[lc].add+=v;
	tr[rc].add+=v;
	tr[lc].sum+=(mid-l+1)*v;
	tr[rc].sum+=(r-mid)*v;
	tr[x].add=0;
}
ll query(int x,int l,int r,int from,int to)
{
	ll res=0;
	if(l==r)
	{
		return tr[x].sum;
	}
//	pushdown(x,l,r);
	if(from<=mid) res+=query(lc,l,mid,from,to);
	if(to>mid) res+=query(rc,mid+1,r,from,to);
	return res;
}
void update(int x,int l,int r,int k,int v)
{
	if(l==k&&k==r)
	{
		tr[x].sum+=(r-l+1)*v;
		tr[x].add+=v;
		return;
	}
//	pushdown(x,l,r);
	if(k<=mid)update(lc,l,mid,k,v);
	else update(rc,mid+1,r,k,v);
	pushup(x);
}
int n;
int m;
signed main()
{
	cin>>n>>m;
	build(1,1,n);
	while(m--)
	{
		char p;
//		cin>>p;
		scanf("%s",&p);
		if(p=='x')
		{
			int x,y;
//			cin>>x>>y;
			scanf("%lld %lld",&x,&y);
			update(1,1,n,x,y);
		}
		else
		{
			int l,r;
			scanf("%lld %lld",&l,&r);
//			cin>>l>>r;
			printf("%lld\n",query(1,1,n,l,r));
//			cout<<query(1,1,n,l,r)<<endl;
		}
	}
	return 0;
}
2024/7/9 17:35
加载中...