社区讨论

萌新刚学OI,求问这个线段树哪里锅了

学术版参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lod2u5v1
此快照首次捕获于
2023/10/30 23:50
2 年前
此快照最后确认于
2023/11/05 10:09
2 年前
查看原帖
一个维护区间最小值,支持区间修改操作的线段树
CPP
class Segment_Tree{
	public:
		int a[60005];
	private:
		int ans[240005],tag[240005];
		inline int lson(int p){return p<<1;}
		inline int rson(int p){return p<<1|1;}
		inline void push_up(int p){ans[p]=min(ans[lson(p)],ans[rson(p)]);}
		inline void push_down(int p){
			tag[lson(p)]+=tag[p];
			tag[rson(p)]+=tag[p];
			ans[lson(p)]+=tag[p];
			ans[rson(p)]+=tag[p];
			tag[p]=0;
		}
	public:
		inline void build(int p,int l,int r){
			if(l==r){ans[p]=a[l];return;}
			int mid=l+r>>1;
			build(lson(p),l,mid);
			build(rson(p),mid+1,r);
			push_up(p);
		}
		inline void add(int p,int l,int r,int nl,int nr,int k){
			if(nl<=l&&nr>=r){ans[p]+=k;tag[p]+=k;return;}
			if(nl>r||nr<l)return;
			push_down(p);
			int mid=l+r>>1;
			add(lson(p),l,mid,nl,nr,k);
			add(rson(p),mid+1,r,nl,nr,k);
			push_up(p);
		}
		inline int ask(int p,int l,int r,int nl,int nr){
			if(nl<=l&&nr>=r)return ans[p];
			if(nl>r||nr<l)return 1<<30;
			push_down(p);
			int mid=l+r>>1,res=1<<30;
			res=min(res,ask(lson(p),l,mid,nl,nr));
			res=min(res,ask(rson(p),mid+1,r,nl,nr));
			return mid;
		}
}tree;

回复

7 条回复,欢迎继续交流。

正在加载回复...