题解 | 小红的区间修改（一）

set和bit都有了,那我来份线段树吧

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

struct node {
    int l, r, sum, lazy;
};

vector<node> tree(1200050);

void bulid(int l, int r, int u){
    tree[u].l = l, tree[u].r = r;
    tree[u].sum = 0, tree[u].lazy = 0;
    if(l == r) return;
    int ul = u << 1, ur = ul | 1, mid = (l + r) >> 1;
    bulid(l, mid, ul), bulid(mid + 1, r, ur);
}

void pushdown(int u){
    if(!tree[u].lazy)return;
    int ul = u << 1, ur = ul | 1;
    tree[ul].lazy += tree[u].lazy;
    tree[ul].sum += (tree[ul].r - tree[ul].l + 1) * tree[u].lazy;
    tree[ur].lazy += tree[u].lazy;
    tree[ur].sum += (tree[ur].r - tree[ur].l + 1) * tree[u].lazy;
    tree[u].lazy = 0;
}


void add(int l, int r, int u){
    if(tree[u].l > r || tree[u].r < l)return;
    if(tree[u].l >= l && tree[u].r <= r){
        tree[u].lazy++;
        tree[u].sum += tree[u].r - tree[u].l + 1;
        return;
    }
    pushdown(u);
    int ul = u << 1, ur = ul | 1;
    add(l, r, ul), add(l, r, ur);
    tree[u].sum = tree[ul].sum + tree[ur].sum;
}

int query(int l, int r, int u){
    if(tree[u].l > r || tree[u].r < l)return 0;
    if(tree[u].l >= l && tree[u].r <= r) return tree[u].sum;
    pushdown(u);
    int ul = u << 1, ur = ul | 1;
    return query(l, r, ul) + query(l, r, ur);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int q, l, r, ans = 0;
    cin >> q;
    bulid(1, 300010, 1);
    while(q--){
        cin >> l >> r;
        if(query(l, r, 1)== 0){
            add(l, r, 1);
            ans = max(ans, r - l + 1);
        }
        cout << ans + 1 << "\n";
    }
    return 0;
}