这个东西怎么改成 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;