线段树区间合并问题

线段树维护区间信息的题单
dalao的博客
最长区间
带修改的严格最长上升子序列长度。【练习线段树做法】
要深入理解线段树的l, r是指的数组下标这句话emm.
一个节点保存：左边的LIS长度， 右边的LIS长度， 区间总体的LIS长度， 区间的元素个数（其实可以算出来）。
关键在于pushup函数：
先更新区间的llis,rlis,tlis.
然后如果左边最右的值<右边最左的值（这个可以用线段树中节点在数组的下标实现，因为l,r指的是下标）：那左右两个区间就可以构成lis,所以可以继续更新：
如果左边的llis==左边的size，代表左边整个是一个最长上升子序列，那llis就可以更新；同理rlis也可以。
最后更新tlis可以是左边的rlis和右边的llis。
tips:可以与LCIS这个题比较一下， 其实这样直接query对于一般区间是不对的，不能简单左右区间答案相加，（例如1 2 3 4 1 2， 查询1到5，并不是4+1）。但是这个题一定是询问1到n的区间，所以可以直接加。

#include
#define ll long long 
using namespace std;
const int N = 100010;
int n,m,w[N];
struct node{
    int l, r, llis,rlis,tlis, sz;
}tr[N << 2];
void pushup(int u){
    tr[u].sz = tr[u << 1].sz + tr[u << 1 | 1].sz;
    tr[u].llis = tr[u << 1].llis;
    tr[u].rlis = tr[u << 1 | 1].rlis;
    tr[u].tlis = max(tr[u << 1].tlis, tr[u << 1 | 1].tlis);
    if(w[tr[u << 1].r] < w[tr[u << 1 | 1].l]){        //严格单调增 
        int mid = tr[u].l + tr[u].r >> 1;
        if(tr[u << 1].llis == tr[u << 1].sz)        //左边整体严格单调增 
            tr[u].llis += tr[u << 1 | 1].llis;
        if(tr[u << 1 | 1].rlis == tr[u << 1 | 1].sz)
            tr[u].rlis += tr[u << 1].rlis;
        tr[u].tlis = max(tr[u].tlis, tr[u << 1].rlis + tr[u << 1 | 1].llis);
    }
}
void build(int u, int l, int r){
    tr[u]= {l, r, 1, 1, 1, 1};
    if(l == r)    return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int x, int v){
    if(tr[u].l == tr[u].r){
        w[x] = v;
        return ;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid)    modify(u << 1, x, v);
    else    modify(u << 1 | 1, x, v);
    pushup(u);
}
int query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r)    return tr[u].tlis;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if(l <= mid)    res += query(u << 1, l, mid);
    if(r > mid)        res += query(u << 1 | 1, mid + 1, r);
    return res;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)    scanf("%d", &w[i]);
    build(1, 1, n);
    printf("%d\n", query(1, 1, n));
    while(m --){
        int x, v;
        scanf("%d%d",&x,&v);
        modify(1, x, v);
        printf("%d\n", query(1, 1, n));
    } 
    return 0;
}

Tunnel Warfare 【线段树区间合并】
几乎是模板题，用这个题来开始线段树区间合并再好不过。 待补充Qwq 2021.4.11没写完
注意pushup和query函数， 并不是和最普通的线段树一样的。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring> 
#include<stack>
#define ll long long
#define ls lmax
#define rs rmax
#define ms tmax
#define len sum
#define Tree tr 
using namespace std;

const int N = 50010;

int n,m,w[N];
stack<int> distory;
struct node{
    int l, r,lmax,rmax,tmax,sum;        //维护左边右边全部的连续1的个数,区间长度
}tr[N << 2];

void pushup(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].lmax = tr[u << 1].lmax, tr[u].rmax = tr[u << 1 | 1].rmax, tr[u].tmax = max(tr[u << 1].tmax, tr[u << 1 | 1].tmax);
    if(w[tr[u << 1].r] == 1){
        if(tr[u << 1].lmax == tr[u << 1].sum)    tr[u].lmax += tr[u << 1 | 1].lmax;
        if(tr[u << 1 | 1].rmax == tr[u << 1 | 1].sum)    tr[u].rmax += tr[u << 1].rmax;
        tr[u].tmax = max(tr[u].tmax, tr[u << 1].rmax + tr[u << 1 | 1].lmax);
    } 
}

void build(int u, int l, int r){
    int tmp = r - l + 1;
    tr[u] = {l, r, tmp, tmp, tmp, tmp};
    if(l == r)    return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int x, int v){
    if(tr[u].l == tr[u].r){
        w[x] = v;
        tr[u] = {tr[u].l, tr[u].r, w[x], w[x], w[x], 1};
    }else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid)    modify(u << 1, x, v);
        else    modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query(int u, int x){        //这个函数很重要Qwq 这个x是会动态变化的， 并不是不变的emm 
    if(tr[u].l == tr[u].r || tr[u].tmax == tr[u].sum || tr[u].tmax == 0)    return tr[u].tmax;
    if(x <= tr[u << 1].r){    //在左边 
        if(x >= tr[u << 1].r - tr[u << 1].rmax + 1)    return query(u << 1, x) + query(u << 1 | 1, tr[u << 1 | 1].l);
        else    return query(u << 1, x);
    } 
    if(x >= tr[u << 1 | 1].l){    //在右边 
        if(x <= tr[u << 1 | 1].lmax + tr[u << 1 | 1].l - 1)    return query(u << 1 | 1, x) + query(u << 1, tr[u << 1].r);
        else    return query(u << 1 | 1, x);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)    w[i] = 1;
    build(1, 1, n);
    while(m --){
        char opt; int x;
        scanf(" %c", &opt);
        if(opt == 'D'){
            scanf("%d", &x);
            modify(1, x, 0);
            distory.push(x);
        }else if(opt == 'R'){
            x = distory.top();
            distory.pop();
            modify(1, x, 1);
        }else{
            scanf("%d", &x);
            printf("%d\n", query(1, x));
        }     
    }
    return 0;
}

LCIS
题意： 求连续最长上升子序列。 注意query的时候不能简单相加， 例如：1 2 5 8 1 2 3 4，查询1->7的区间时，左边的tlics是4，右边的是3，但是答案并不是简单的4 + 3. 所以返回结构体方便书写。
注意ans结构体要赋予l,r的值！

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 100010;

int n,m,t,w[2 * N];
struct node{
    int l, r, llcis, rlcis, tlcis, sz;
}tr[N << 2];

void pushup(node& rt, node& ls, node& rs){
    rt.llcis = ls.llcis, rt.rlcis = rs.rlcis, rt.tlcis = max(ls.tlcis, rs.tlcis), rt.sz = ls.sz + rs.sz;
    if(w[ls.r] < w[rs.l]){
        if(ls.tlcis == ls.sz)    rt.llcis += rs.llcis;
        if(rs.tlcis == rs.sz)    rt.rlcis += ls.rlcis;
        rt.tlcis = max(rt.tlcis, ls.rlcis + rs.llcis);
    }
}
void pushup(int u){
    node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    pushup(rt, ls, rs);
}

void build(int u, int l, int r){
    tr[u] = {l, r, 1, 1, 1, 1};
    if(l == r)    return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int x, int v){
    if(tr[u].l == tr[u].r)    w[x] = v;
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid)    modify(u << 1, x, v);
        else    modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

void show(node x){
    printf("l = %d r = %d tlcis = %d\n", x.l, x.r, x.tlcis);
}

node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r)    return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if(r <= mid)    return query(u << 1, l, r);
    if(l > mid)        return query(u << 1 | 1, l, r);
    else{
        node n1, n2, ans;
        ans.l = tr[u].l, ans.r = tr[u].r;
        n1 = query(u << 1, l, r);
        n2 = query(u << 1 | 1, l, r);
        pushup(ans, n1, n2);
        return ans;
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)    scanf("%d", &w[i]);
    build(1, 1, n);
    while(m --){
        char op[20];
        int x, y;
        scanf(" %s%d%d", op, &x, &y); x ++;
        if(op[0] == 'Q')    y ++, printf("%d\n", query(1, x, y).tlcis);
        else    modify(1, x, y);
    }
}

int main(){
    cin >> t;
    while(t --)    solve();
    return 0;    
}

Can you answer these queries III
区间最大连续子段和， 注意query返回node节点。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 500010, inf = 1e9 + 7;

int n,m,w[N];
struct node{
    int l,r,lmax,rmax,tmax,sum;
}tr[N << 2];

void pushup(node& root, node& ls, node& rs){
    root.sum = ls.sum + rs.sum;
    root.lmax = max(ls.lmax, ls.sum + rs.lmax);
    root.rmax = max(rs.rmax, rs.sum + ls.rmax);
    root.tmax = max(max(ls.tmax, rs.tmax), ls.rmax + rs.lmax);
}
void pushup(int u){
    node& root = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    pushup(root, ls, rs);
}

void build(int u, int l, int r){
    tr[u] = {l, r, w[l], w[l], w[l], w[l]};
    if(l == r)    return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int x, int v){
    if(tr[u].l == tr[u].r)    tr[u] = {x, x, v, v, v, v};
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid)    modify(u << 1, x, v);
        else    modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

//node query(int u, int l, int r){            //这样也可以
//    if(tr[u].l >= l && tr[u].r <= r)    return tr[u];
//    int mid = tr[u].l + tr[u].r >> 1;
//    if(r <= mid)    return query(u << 1, l, r);
//    else if(l > mid)        return query(u << 1 | 1, l, r);
//    else{
//        node n1, n2, res;
//        n1 = query(u << 1, l, r);
//        n2 = query(u << 1 | 1, l, r);
//        pushup(res, n1, n2);
//        return res;
//    }
//}
node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r)    return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    node n1 = {0,0,-inf,-inf,-inf,0}, n2 = {0,0,-inf,-inf,-inf,0}, res;
    if(l <= mid)    n1 = query(u << 1, l, r);
    if(r > mid)        n2 = query(u << 1 | 1, l, r);
    pushup(res, n1, n2);
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)    scanf("%d", &w[i]);
    build(1, 1, n);
    while(m --){
        int opt, x, y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt == 1){
            if(x > y) swap(x, y);
            printf("%d\n", query(1,x,y).tmax);
        }    
        else    modify(1,x,y);
    }
    return 0;
}

Hotel---poj3667/洛谷
题意：题意：酒店有n个房间，现有m个团队，每个团队需要连续 d 个房间，现在有两个操作，1：需要 d 个房间，2：从 x 开始连续 d 个房间退房；
当是1的时候，需要d个房间时， 我们尽可能的找到最靠左的房间给客人，输出最左边房间的编号。
线段树区间合并+区间修改。
维护当前区间的连续空床数。
注意query的时候，分成三类：
A. 左边区间连续空床数>=len， 递归往左边查询；
B. 中间区间连续空床数>=len, 答案就是左边区间的坐标（因为要下标最小， 所以直接tr[u << 1].r - tr[u << 1].rsum + 1;
C. 以上不满足，往右边查询。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 50010;

int n,m;
struct node{
    int l, r, lsum, rsum, tsum, sz, lazy;
}tr[N];

void pushup(int u){
    node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    rt.lsum = ls.lsum, rt.sz = ls.sz + rs.sz, rt.rsum = rs.rsum;
    if(ls.tsum == ls.sz)    rt.lsum += rs.lsum;
    if(rs.tsum == rs.sz)    rt.rsum += ls.rsum;
    rt.tsum = max(max(ls.tsum, rs.tsum), ls.rsum + rs.lsum);
}

void build(int u, int l, int r){
    tr[u] = {l, r, 1, 1, 1, 1, 0};
    if(l == r)    return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void pushdown(int u){
    node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    if(rt.lazy == 0)    return ;
    if(rt.lazy == 1){    // 要住人, 全满 
        ls.lazy = rs.lazy = 1;
        ls.lsum = ls.rsum = ls.tsum = 0;
        rs.lsum = rs.rsum = rs.tsum = 0;
    }else{                // 要退房， 全空 
        ls.lazy = rs.lazy = 2;
        ls.lsum = ls.rsum = ls.tsum = ls.sz;
        rs.lsum = rs.rsum = rs.tsum = rs.sz;
    }
    rt.lazy = 0;
}

void update(int u, int l, int r, int v){
    if(tr[u].l >= l && tr[u].r <= r){
        if(v == 1)    tr[u].lsum = tr[u].rsum = tr[u].tsum = 0;        //要入住
        else    tr[u].lsum = tr[u].rsum = tr[u].tsum = tr[u].sz;     //要退房 
        tr[u].lazy = v;
    }else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)    update(u << 1, l, r, v);
        if(r > mid)        update(u << 1 | 1, l, r, v);
        pushup(u);
    }
}

int query(int u, int l, int r, int len){
    pushdown(u);
    if(tr[u].l == tr[u].r)    return tr[u].l;
    int mid = tr[u].l + tr[u].r >> 1;
    if(tr[u << 1].tsum >= len)    return query(u << 1, l, r, len);
    if(tr[u << 1].rsum + tr[u << 1 | 1].lsum >= len)    return tr[u << 1].r - tr[u << 1].rsum + 1;
    return query(u << 1 | 1, l, r, len);
}

int main(){
    cin >> n >> m;
    build(1, 1, n);
    while(m --){
        int opt, x, y;
        //printf("re: %d\n", tr[1].tsum);
        scanf("%d%d",&opt,&x);
        if(opt == 1){
            if(tr[1].tsum >= x){
                int tmp = query(1, 1, n, x);
                printf("%d\n", tmp);
                update(1, tmp, tmp + x - 1, 1);
            }else    puts("0");
        }else{
            scanf("%d",&y);
            update(1, x, x + y - 1, 2); 
        }
    }
    return 0;
}

线段树求LIS(权值线段树维护dp的最大值)
896. 最长上升子序列 II
tips:注意要求严格单调增， query函数注意。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 100010;

int n, idx, mx, a[N], ans = 1;
struct node{
    int l, r, maxx;
}tr[N << 2];
vector<int> nums;

int pushup(int u){ tr[u].maxx = max(tr[tr[u].l].maxx, tr[tr[u].r].maxx);}
int build(int l, int r){
    int p = ++ idx;
    if(l == r)    return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
} 
void update(int u, int l, int r, int p, int x){
    if(l == r)    tr[u].maxx = max(tr[u].maxx, x);
    else{
        int mid = l + r >> 1;
        if(p <= mid)    update(tr[u].l, l, mid, p, x);
        else    update(tr[u].r, mid + 1, r, p, x);
        pushup(u);
    }
}
int query(int u, int l, int r, int p){
    if(p > r)    return tr[u].maxx;
    if(l == r)  return l == p ? 0 : tr[u].maxx;
    int mid = l + r >> 1;
    int ans = query(tr[u].l, l, mid, p);
    if(p > mid)    ans = max(ans, query(tr[u].r, mid + 1, r, p));
    return ans;
}
int get(int x){ return lower_bound(nums.begin(), nums.end(), x) - nums.begin();}

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    mx = nums.size() - 1;
    build(0, mx);
    for(int i = 1; i <= n; ++ i){
        int now = query(1, 0, mx, get(a[i])) + 1;
        ans = max(ans, now);
        update(1, 0, mx, get(a[i]), now);
    }
    cout << ans;
    return 0;
}

LIS
树状数组版：

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 100010;

int n,m,tr[N],ans,dp[N];

int lowbit(int x){ return x & (-x);}
int ask(int x){ int res = 0; for(int i = x; i >= 1; i -= lowbit(i)) res = max(res, tr[i]) ; return res; }
void add(int x, int v){ for(int i = x; i <= n; i += lowbit(i))    tr[i] = max(tr[i], v);}

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i){
        int x;
        scanf("%d", &x);
        dp[i] = ask(x - 1) + 1;
        add(x, dp[i]);
    }
    for(int i = 1; i <= n; ++ i)    ans = max(ans, dp[i]);
    cout << ans;
    return 0; 
}

F Fundraising 【离散化树状数组维护二维带权最长上升子序列】
tips:也可以用离散化权值线段树。
这个题是友好城市 的扩展版，不但数据范围加强，而且带权、不能重叠、需要离散化处理。
思路： 先按照某一个维度排序，这样就可以忽略某一维度的信息了（升序排序，一定可以保证这一维度数据上升）， 然后对于两个维度都相同的点，将他们的权值合并； 对于第一维度相同但第二维度不同的点，按照第二维度从大到小排序（这样可以保证第一维度相同的点不会影响答案， 可以画图看看正确性）。然后用树状数组维护即可。
树状数组版：

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 100010;

int n,m,mx;
ll w[N],tr[N],ans;
vector<ll> nums;
struct node{
    int x, y;
    ll w;
}a[N];
int cmp(node n1, node n2){ return n1.x == n2.x ? n1.y > n2.y : n1.x < n2.x;}
int lowbit(int x){ return x & (-x);}
ll ask(int x){
    ll res = 0;
    for(int i = x - 1; i >= 1; i -= lowbit(i))  res = max(res, tr[i]);  //因为要求严格单调，从前一个位置开始查
    return res;
}
int add(int x, ll c){for(int i = x; i <= mx; i += lowbit(i))    tr[i]  = max(tr[i], c);}

int get(int x){ return lower_bound(nums.begin(), nums.end(), x) - nums.begin();}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ){
        scanf("%d%d%lld",&a[i].x, &a[i].y, &a[i].w);
        nums.push_back(a[i].y);     //离散化第二维度即可， 第一维度是排序关键字
    } 
    sort(a + 1, a + 1 + n, cmp);
    nums.push_back(-1);             //为了让下标从1开始
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    mx = nums.size();
    for(int i = 1; i <= n; ++ i){
        if(i < n && a[i].x == a[i + 1].x && a[i].y == a[i + 1].y){  //对于两个维度都相同的点，进行合并
            a[i + 1].w += a[i].w;   
            continue;
        }
        int id = get(a[i].y);
        ll tmp = ask(id) + a[i].w;
        ans = max(ans, tmp);
        add(id, tmp);
    }
    cout << ans;
    return 0;
}

权值线段树版：

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 100010;

int n,m,mx,idx;
ll ans;
vector<ll> nums;
struct node{
    int x, y;
    ll w;
}a[N];
int cmp(node n1, node n2){ return n1.x == n2.x ? n1.y > n2.y : n1.x < n2.x;}
struct Tr{
    int l, r;
    ll maxx;
}tr[N << 2];

void pushup(int u){tr[u].maxx = max(tr[tr[u].l].maxx, tr[tr[u].r].maxx);}
int build(int l, int r){
    int p = ++ idx;
    if(l == r)  return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}
void modify(int u, int l, int r, int p, ll v){
    if(l == r)  tr[u].maxx = max(tr[u].maxx, v);
    else{
        int mid = l + r >> 1;
        if(p <= mid)    modify(tr[u].l, l, mid, p, v);
        else    modify(tr[u].r, mid + 1, r, p, v);
        pushup(u);
    }
}
ll query(int u, int l, int r, int p){
    if(p > r)   return tr[u].maxx;
    if(p == l && p == r)    return 0;
    int mid = l + r >> 1;
    ll ans = query(tr[u].l, l, mid, p);
    if(p > mid) ans = max(ans, query(tr[u].r, mid + 1, r, p));
    return ans;
}

int get(int x){ return lower_bound(nums.begin(), nums.end(), x) - nums.begin();}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ){
        scanf("%d%d%lld",&a[i].x, &a[i].y, &a[i].w);
        nums.push_back(a[i].y);     //离散化第二维度即可， 第一维度是排序关键字
    } 
    sort(a + 1, a + 1 + n, cmp);
    nums.push_back(-1);             //为了让下标从1开始
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    mx = nums.size();
    build(1, mx);
    for(int i = 1; i <= n; ++ i){
        if(i < n && a[i].x == a[i + 1].x && a[i].y == a[i + 1].y){  //对于两个维度都相同的点，进行合并
            a[i + 1].w += a[i].w;   
            continue;
        }
        int id = get(a[i].y);
        ll tmp = query(1, 1, mx, id) + a[i].w;
        ans = max(ans, tmp);
        modify(1, 1, mx, id, tmp);
    }
    cout << ans;
    return 0;
}

POJ - 2777 Count Color 【线段树维护区间不同数的个数】
题意：
给出一个序列，一开始都是数字1代表第一种颜色，最多有30种颜色，现在有两种操作：
1 x y col将区间[x,y]的气球都变成颜色col
2 x y 查询区间内不同颜色的气球个数
tips:这个题颜色个数很小，只有30个，可以直接二进制状压表示颜色即可。
将一个区间全部变成某个颜色时，pushdown时直接让左右孩子的颜色等于lazy的颜色即可。
注意query函数并不是简单的相加（可以左右区间的颜色相同）
注意了解:
__builtin_popcount()用于计算一个 32 位无符号整数有多少个位为1

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long 
using namespace std;

const int N = 100010;

struct node{
    int l, r,color, lazy;
}tr[N << 2];
int n,m,k;

void pushup(int u){ tr[u].color = tr[u << 1].color | tr[u << 1 | 1].color; }
void pushdown(int u){
    if(tr[u].lazy){
        tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
        tr[u << 1].color = tr[u << 1 | 1].color = tr[u].lazy;
        tr[u].lazy = 0;
    }
}
void build(int u, int l, int r){
    tr[u] = {l, r, 1, 0};
    if(l == r)  return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update(int u, int l, int r, int v){
    if(tr[u].l >= l && tr[u].r <= r)    tr[u].lazy = tr[u].color = 1 << (v - 1);
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if(l <= mid)    update(u << 1, l, r, v);
        if(r > mid)     update(u << 1 | 1, l, r, v);
        pushup(u);
    }
}
node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) {
        //printf("--l = %d r = %d co = %d\n", tr[u].l, tr[u].r, tr[u].color);
        return tr[u];
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    node n1, n2, res;
    if(r <= mid)    return query(u << 1, l, r);
    if(l > mid)     return  query(u << 1 | 1, l, r);
    else{
        n1 = query(u << 1, l, r);
        n2 = query(u << 1 | 1, l, r);
        res.color = n1.color | n2.color;
        return res;
    }
}

int main(){
    cin >> n >> k >> m;
    build(1, 1, n);
    while (m -- ){
        char op;    int x, y, z;
        scanf(" %c%d%d",&op,&x,&y);
        if(x > y)   swap(x, y);
        if(op == 'C'){
            scanf("%d", &z);
            update(1, x, y, z);
            //printf("--%d\n", query(1, x, y));
        }else   printf("%d\n", __builtin_popcount(query(1, x, y).color));
    }
    return 0;
}

Codeforces Beta Round #43 D. Parking Lot
题意： 有一条长度为L的街道,有N个操作,操作有两种,（1）"1 a"，表示有一辆长度为a的车开进来想找停车位,停车位必须满足与它前面的车距离至少为b,与后面的车距离至少为f.如果能找到这样的停车位,输出这辆车的起始位置(且这个位置最小),否则输出-1。（2）"2 a"，表示第a个事件里进来停车的那辆车开出去了。
tips：当一辆车停进来的时候，要满足前后的间距要求；但是这辆车停下，下一辆车停好后，可能不满足前一辆车的间距要求了！ 例如b = 1, f = 2，前一辆车所在区间是[3,6],下一辆车可以从7开始停车（只需要满足7 - b >= 6即可）。
注意最开始的位置不需要满足与后面间隔是b的条件， 而最后一辆车也不需要满足和前面间隔是f的条件（这一点可以通过建立n + b + f长度的线段树来解决）。询问的时候询问len + b + f, 而修改的时候只修改len(b,f只是间隔)
注意query函数， 其他就是和hotel一样的写法。

#include<bits/stdc++.h>
#define PII pair<int, int>
#define x first
#define y second
#define ll long long 
using namespace std;

const int N = 100210;

int n,m,b,f,car;
PII park[N];
struct node{
    int l, r, lsum, rsum, tsum, sz, lazy;
}tr[N << 2];

void pushup(int u){
    node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    rt.lsum = ls.lsum, rt.rsum = rs.rsum, rt.sz = ls.sz + rs.sz;
    if(ls.tsum == ls.sz)    rt.lsum += rs.lsum;
    if(rs.tsum == rs.sz)    rt.rsum += ls.rsum;
    rt.tsum = max(max(ls.tsum, rs.tsum), ls.rsum + rs.lsum);
}
void build(int u, int l, int r){
    tr[u] = {l, r, 1, 1, 1, 1, 0};
    if(l == r)    return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
} 
void pushdown(int u){
    node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    if(rt.lazy){
        ls.lazy = rt.lazy, rs.lazy = rt.lazy;
        if(rt.lazy == 1){        //parking
            ls.lsum = ls.rsum = ls.tsum = 0;
            rs.lsum = rs.rsum = rs.tsum = 0;
        }else{        //leaving
            ls.lsum = ls.rsum = ls.tsum = ls.sz;
            rs.lsum = rs.rsum = rs.tsum = rs.sz;
        }
        rt.lazy = 0;
    }
}
void update(int u, int l, int r, int v){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].lazy = v;
        if(v == 1)    tr[u].lsum = tr[u].rsum = tr[u].tsum = 0;
        else    tr[u].lsum = tr[u].rsum = tr[u].tsum = tr[u].sz;
    }else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)    update(u << 1, l, r, v);
        if(r > mid)        update(u << 1 | 1, l, r, v);
        pushup(u);
    }
}
int query(int u, int l, int r, int len){
    pushdown(u);
    if(tr[u].l == 1 && tr[u].lsum + b >= len)    return 1;     //最头上不需要管b的间隔
    if(tr[u].l == tr[u].r)    return tr[u].l;
    int mid = tr[u].l + tr[u].r >> 1;
    if(tr[u << 1].tsum >= len)    return query(u << 1, l, r, len);
    if(tr[u << 1].rsum + tr[u << 1 | 1].lsum >= len)    return tr[u << 1].r - tr[u << 1].rsum + 1;
    return query(u << 1 | 1, l, r, len);
}

int main(){
    cin >> n >> b >> f;
    build(1, 1, n + b + f);
    cin >> m;
    for(int z = 1; z <= m; ++ z){
        int opt, x;
        scanf("%d%d",&opt,&x);
        if(opt == 1){
            if(tr[1].tsum < x + b + f)    puts("-1");
            else{
                int tmp = query(1, 1, n + b + f, x + b + f);
                if(tmp != 1)    tmp += b;
                if(tmp + x - 1 > n){
                    puts("-1");
                    continue ;
                }
                park[z] = {tmp - 1, tmp + x};
                printf("%d\n", tmp - 1);
                update(1, tmp, tmp + x - 1, 1);
            }
        }else{
            PII now = park[x];
            update(1, now.x, now.y, 2);
        }
    }
    return 0;
}

hdu3397 Sequence operation 【毒瘤】
题意： 有N个为0或为1的数，有M个操作，操作有5种类型。（1）“0 a b”，表示将区间[a,b]范围内的数全部置0。（2）“1 a b”，表示将区间[a,b]内的数全部置1。（3）"2 a b"，表示将区间[a,b]内的数0变成1，1变成0。（4）"3ab"，表示查询[a,b]范围内1的数。（5）"4 a b"，表示查询[a,b]范围内最长的连续的1。
思路：区间合并的综合应用。
维护左边、右边、总体连续的1、0，1、0的个数等。
注意如果某个点有reverse标记，然后上面下传了lazy,那就把这个reverse去掉（这里非常重要。如果不去，下面那个操作的pushdown可能会因为这里的reverse而超时），因为一定会被全部变成lazy，没有必要翻转了；如果某个点有lazy标记，上面下传了reverese,则先pushdown(ls,rs),把这个子树的lazy标记全部下放（如果孩子的孩子也有lazy，那就继续下放），再reverse,这样可以保证不错（否则lazy和reverse会乱）。
然后就是常规的区间合并。

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long 
using namespace std;

const int N = 100010;

struct node{
    int l, r, sz, sz1, sz0, llen1, llen0, rlen1, rlen0, tlen1, tlen0, lazy, reverse;
}tr[N * 6];
int n,w[N],m,t;

void pushup(node& rt, node& ls, node& rs){
    rt.sz = ls.sz + rs.sz, rt.sz1 = ls.sz1 + rs.sz1, rt.sz0 = ls.sz0 + rs.sz0;
    rt.llen1 = ls.llen1, rt.llen0 = ls.llen0, rt.rlen1 = rs.rlen1, rt.rlen0 = rs.rlen0;
    rt.tlen1 = max(max(ls.tlen1, rs.tlen1), ls.rlen1 + rs.llen1), rt.tlen0 = max(max(ls.tlen0, rs.tlen0), ls.rlen0 + rs.llen0);
    if(ls.tlen1 == ls.sz)   rt.llen1 += rs.llen1;
    if(ls.tlen0 == ls.sz)   rt.llen0 += rs.llen0;
    if(rs.tlen1 == rs.sz)   rt.rlen1 += ls.rlen1;
    if(rs.tlen0 == rs.sz)   rt.rlen0 += ls.rlen0;
}
void pushup(int u){ pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); }
void build(int u, int l, int r){
    tr[u] = {l, r, 1, w[l] == 1, w[l] == 0, w[l] == 1, w[l] == 0, w[l] == 1, w[l] == 0, w[l] == 1, w[l] == 0, -1, 0};
    if(l == r)  return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void Swap(node& rt){ swap(rt.llen0, rt.llen1), swap(rt.rlen1, rt.rlen0), swap(rt.tlen0, rt.tlen1);swap(rt.sz0, rt.sz1);}
void pushdown(int u){
    node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    if(rt.l == rt.r)    return ;
    if(rt.reverse){
        pushdown(u << 1);    pushdown(u << 1 | 1);
        Swap(ls);   Swap(rs);
        ls.reverse ^= 1, rs.reverse ^= 1;
        rt.reverse = 0;
    } 
    if(rt.lazy != -1){
        ls.reverse = rs.reverse = 0;
        if(rt.lazy == 1){   //全变成1
            ls.lazy = rs.lazy = 1;
            ls.sz1 = ls.sz, rs.sz1 = rs.sz, ls.sz0 = rs.sz0 = 0;
            ls.llen1 = ls.rlen1 = ls.tlen1 = ls.sz;
            ls.llen0 = ls.rlen0 = ls.tlen0 = 0;
            rs.llen1 = rs.rlen1 = rs.tlen1 = rs.sz;
            rs.llen0 = rs.rlen0 = rs.tlen0 = 0;
        }else if(rt.lazy == 0){ //全变成0
            ls.lazy = rs.lazy = 0;
            ls.sz0 = ls.sz, rs.sz0 = rs.sz, ls.sz1 = rs.sz1 = 0;
            ls.llen0 = ls.rlen0 = ls.tlen0 = ls.sz;
            ls.llen1 = ls.rlen1 = ls.tlen1 = 0;
            rs.llen0 = rs.rlen0 = rs.tlen0 = rs.sz;
            rs.llen1 = rs.rlen1 = rs.tlen1 = 0;
        }
        rt.lazy = -1;
    }
}

void update(int u, int l, int r, int v){
    node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    if(tr[u].l >= l && tr[u].r <= r){
        if(v == 1)  rt.lazy = 1, rt.reverse = 0, rt.sz1 = rt.sz, rt.sz0 = 0, rt.llen1 = rt.rlen1 = rt.tlen1 = rt.sz, rt.llen0 = rt.rlen0 = rt.tlen0 = 0;
        else if(v == 0) rt.lazy = 0, rt.reverse = 0, rt.sz0 = rt.sz, rt.sz1 = 0, rt.llen0 = rt.rlen0 = rt.tlen0 = rt.sz, rt.llen1 = rt.rlen1 = rt.tlen1 = 0;
        else{       
            if(rt.lazy != -1)   rt.lazy ^= 1;
            rt.reverse ^= 1;
            Swap(rt);
        }
    }else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)    update(u << 1, l, r, v);
        if(r > mid)     update(u << 1 | 1, l, r, v);
        pushup(u);
    }
}
node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r)    return tr[u];
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(r <= mid)    return query(u << 1, l, r);
    else if(l > mid)    return query(u << 1 | 1, l, r);
    else{
        node n1 = query(u << 1, l, r);
        node n2 = query(u << 1 | 1, l, r);
        node res = {l,r,0,0,0,0,0,0,0,0,0,-1,0}; pushup(res, n1, n2);
        return res;
    }
}

int main(){
    cin >> t;
    while(t --){
        cin >> n >> m;
        for(int i = 1; i <= n; ++ i)    scanf("%d",&w[i]);
        build(1, 1, n);
        while(m --){
            int op, x, y;
            scanf("%d%d%d",&op,&x,&y);  x ++, y ++;
            if(op == 0)         update(1, x, y, 0);
            else if(op == 1)    update(1, x, y, 1);
            else if(op == 2)    update(1, x, y, 2);
            else if(op == 3)    printf("%d\n", query(1, x, y).sz1);
            else{
                node n1 = query(1, x, y);
                printf("%d\n", n1.tlen1);
            }    
        }
    }
    return 0;
}