线段树求调
  • 板块学术版
  • 楼主isop
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/5/28 20:57
  • 上次更新2024/5/28 23:32:02
查看原帖
线段树求调
1071516
isop楼主2024/5/28 20:57

宏定义u<<1处报错

#include<bits/stdc++.h>
using namespace std;
#define lc u<<1
#define rc u<<1|1
#define mid (tree[u].l+tree[u].r) >>1
typedef long long ll;

const int N=1e5+10;
int n,m;
int a[N];
struct node
{
	int l,r;
	ll data;
	int add;
}tree[N<<2];

inline ll read()
{
	ll a=0,f=1;
	char c=getchar();
	while(!isdigit(c)) f=-1,c=getchar();
	while(isdigit(c)) a=(a<<3)+(a<<1)+(c^'0'),c=getchar();
	return a*f;
}

inline void write(ll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
 
node pushup(node lc,node rc)
{
	node rt;
	rt.data=lc.data+rc.data;
}

inline node pushdown(int u)//懒惰 
{
	if(tree[u].add)
	{
		tree[lc].data+=tree[u].add*(tree[lc].r-tree[lc].l+1);
		tree[rc].data+=tree[u].add*(tree[rc].r-tree[rc].l+1);
		tree[lc].add+=tree[u].add;
		tree[rc].add+=tree[u].add;
		tree[u].add=0;
	}
}

inline void build(int u,int l,int r)
{
	tree[u]={l,r,a[l]};
	if(l==r) return;
	build(lc,l,mid);
	build(rc,mid+1,r);
	tree[u]=pushup(tree[lc],tree[rc]);
}

inline node query(int u,int fl,int fr)
{
	if(fl<=tree[u].l && tree[u].r<=fr) return tree[u];
	if(fr<=mid) return query(lc,fl,fr);
	else if(fl>mid) return query(rc,fl,fr);
	else return pushup(query(lc,fl,fr),query(rc,fl,fr));
}

inline void modify(int u,int x,int y,int k)//区间修改 
{
	if(x<=tree[u].l && tree[u].r<=y)
	{
		tree[u].data+=(tree[u].r-tree[u].l+1)*k;
		tree[u].add+=k;
		return;
	}
	pushdown(u);
	if(x<=mid) modify(lc,x,y,k);
	if(y>mid) modify(rc,x,y,k);
	tree[u]=pushup(tree[lc],tree[rc]);
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	int opt;
	while(m--)
	{
		opt=read();
		if(opt==1)
		{
			int x,y,k;
			modify(1,x,y,k);
		}
		else
		{
			write(query(1,x,y).data);
			printf("\n");
		}
	}
	return 0;
}
2024/5/28 20:57
加载中...