关于线段树的写法
  • 板块学术版
  • 楼主黑客
  • 当前回复13
  • 已保存回复13
  • 发布时间2020/12/3 10:49
  • 上次更新2023/11/5 06:49:47
查看原帖
关于线段树的写法
189394
黑客楼主2020/12/3 10:49

我的线段树是这么写的:

struct node{
	int Min,sum,cnt;
}val[N<<2];
int lazy[N<<2];
node operator + (const node &x,const node &y){
	if(x.Min<y.Min)return x;
	else if(y.Min<x.Min)return y;
	return (node){x.Min,x.sum+y.sum,x.cnt+y.cnt};
}
void build(int x,int l,int r){
	if(l==r){
		val[x]=(node){0,l,1};
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	val[x]=val[ls]+val[rs];
}
void down(int x){
	if(!lazy[x])return;
	val[ls].Min+=lazy[x];
	val[rs].Min+=lazy[x];
	lazy[ls]+=lazy[x];
	lazy[rs]+=lazy[x];
	lazy[x]=0;
}
void update(int x,int l,int r,int xl,int xr,int v){
	if(l==xr&&r==xr){
		tot++;
		val[x].Min+=v;
		lazy[x]+=v;
		return;
	}
	down(x);
	int mid=(l+r)>>1;
	if(xr<=mid)update(ls,l,mid,xl,xr,v);
	else if(xl>mid)update(rs,mid+1,r,xl,xr,v);
	else update(ls,l,mid,xl,mid,v),update(rs,mid+1,r,mid+1,xr,v);
	val[x]=val[ls]+val[rs];
}
node query(int x,int l,int r,int xl,int xr){
	if(l==xl&&r==xr){
		return val[x];
	}
	down(x);
	int mid=(l+r)>>1;
	if(xr<=mid)return query(ls,l,mid,xl,xr);
	else if(xl>mid)return query(rs,mid+1,r,xl,xr);
	else return query(ls,l,mid,xl,mid)+query(rs,mid+1,r,mid+1,xr);
}

但是今天写题的时候T了,请问这样写有什么问题吗?被机房巨佬暴D了qwq

2020/12/3 10:49
加载中...