求问 zkw 线段树(不是求调)赏关
  • 板块学术版
  • 楼主Muse_Dash
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/6 08:19
  • 上次更新2024/8/6 09:51:25
查看原帖
求问 zkw 线段树(不是求调)赏关
776633
Muse_Dash楼主2024/8/6 08:19

这个东西怎么改成 zkw 线段树?

其实我是懒得学

struct sgm{
	#define lc (x<<1)
	#define rc (x<<1|1)
	int tag[N<<2],mn[N<<2];
	inline void push_up(int x){
		mn[x]=min(mn[lc],mn[rc]);
	}
	inline void push_down(int x){
		if (!tag[x]) return;
		tag[lc]+=tag[x],tag[rc]+=tag[x];
		mn[lc]+=tag[x],mn[rc]+=tag[x];
		tag[x]=0;
	}
	void update(int x,int l,int r,int ql,int qr,int d){
		if (ql>qr) return;
		if (ql<=l&&qr>=r){
			tag[x]+=d,mn[x]+=d;
			return;
		}
		push_down(x);
		int mid=(l+r)>>1;
		if (ql<=mid) update(lc,l,mid,ql,qr,d);
		if (qr>mid) update(rc,mid+1,r,ql,qr,d);
		push_up(x);
	}
	int query(int x,int l,int r){
		if (l==r) return l;
		push_down(x);
		int mid=(l+r)>>1;
		if (!mn[lc]) return query(lc,l,mid);
		else return query(rc,mid+1,r);
	}
	#undef lc
	#undef rc
}book;
2024/8/6 08:19
加载中...