社区讨论
萌新刚学OI,求问这个线段树哪里锅了
学术版参与者 5已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @lod2u5v1
- 此快照首次捕获于
- 2023/10/30 23:50 2 年前
- 此快照最后确认于
- 2023/11/05 10:09 2 年前
一个维护区间最小值,支持区间修改操作的线段树
CPPclass 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 条回复,欢迎继续交流。
正在加载回复...