线段树模板
线段树区间更新询问区间和模板
int Case = 1, n, m;
struct {
int l, r;
ll lazy, val;
int mid(){return(l+r)/2;}
int size(){return r-l+1;}
}tr[maxn<<2];
void pushup(int rt){tr[rt].val = tr[rt<<1].val+tr[rt<<1|1].val;}
void pushdown(int rt) {
ll &x = tr[rt].lazy;
tr[rt<<1].lazy = tr[rt<<1|1].lazy = x;
tr[rt<<1].val = x*tr[rt<<1].size();
tr[rt<<1|1].val = x*tr[rt<<1|1].size();
x = -1;
}
void build(int rt, int l, int r) {
tr[rt].l = l; tr[rt].r = r;tr[rt].lazy = -1;tr[rt].val = 0;
if(l == r) return;///
int mid = tr[rt].mid();
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
pushup(rt);
}
void update(int rt, int l, int r, ll x) {
if(tr[rt].l == l && tr[rt].r == r) {
tr[rt].val = x*tr[rt].size();tr[rt].lazy = x;return;
}
if(tr[rt].lazy!= -1) pushdown(rt);
int mid = tr[rt].mid();
if(r <= mid) update(rt<<1, l, r, x);
else if(l > mid) update(rt<<1|1, l, r, x);
else update(rt<<1, l, mid, x),update(rt<<1|1, mid+1, r, x);
pushup(rt);
}
int query(int rt, int l, int r) {
if(tr[rt].l == l && tr[rt].r == r) return tr[rt].val;
if(tr[rt].lazy != -1) pushdown(rt);
int mid = tr[rt].mid();
if(r <= mid) return query(rt<<1, l, r);
else if(l > mid) return query(rt<<1|1, l, r);
else return query(rt<<1, l, mid)+query(rt<<1|1, mid+1, r);
pushup(rt);
}
询问区间第一个大于x的数
int query(int rt, int l, int r, int x){
if(tr[rt].mx <= x || l > r) return -1;
if(tr[rt].l == tr[rt].r) return tr[rt].l;
int mid = tr[rt].mid();
if(mid >= r) return query(rt<<1, l, r, x);
else if(mid < l) return query(rt<<1|1, l, r, x);
else {
int t = query(rt<<1, l, mid, x);
if(t==-1) return query(rt<<1|1, mid+1, r, x);
else return t;
}
}