信息学做题日记：为啥没能脑洞？短路了呗

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
struct line {
    int l, r;
    int sum, len, add, w, lmax, rmax, ans;
} t[4 * maxn];

void push_up(int u) {
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
    t[u].lmax = t[u << 1].lmax;
    t[u].lmax += t[u << 1].lmax == t[u << 1].len ? t[u << 1 | 1].lmax : 0;
    t[u].rmax = t[u << 1 | 1].rmax;
    t[u].rmax += t[u << 1 | 1].rmax == t[u << 1 | 1].len ? t[u << 1].rmax : 0;
    t[u].ans = max({t[u << 1].ans, t[u << 1 | 1].ans, t[u << 1].rmax + t[u << 1 | 1].lmax});
}

void build(int u, int l, int r) {
    t[u].l = l;
    t[u].r = r;
    t[u].len = r - l + 1;
    t[u].add = -1;
    if (l == r) {
        t[u].sum = 1;
        t[u].lmax = 0;
        t[u].rmax = 0;
        t[u].ans = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

void change(line &x, int len, int s, int add) {
    x.ans = len;
    x.lmax = len;
    x.rmax = len;
    x.sum = s;
    x.add = add;
}

void push_down(int u) {
    auto &root = t[u];
    auto &left = t[u << 1];
    auto &right = t[u << 1 | 1];
    if (root.add == 0) {
        change(left, left.len, 0, 0);
        change(right, right.len, 0, 0);
    } else if (root.add == 1) {
        change(left, 0, left.len, 1);
        change(right, 0, right.len, 1);
    }
    root.add = -1;
}

void modify(int u, int l, int r, int opt) {
    if (t[u].l >= l && t[u].r <= r) {
        opt == 0 ? change(t[u], t[u].len, 0, 0) : change(t[u], 0, t[u].len, 1);
    } else {
        push_down(u);
        int mid = (t[u].l + t[u].r) >> 1;
        if (mid >= l) {
            modify(u << 1, l, r, opt);
        }
        if (mid < r) {
            modify(u << 1 | 1, l, r, opt);
        }
        push_up(u);
    }
}

int query(int u, int l, int r, int opt) {
    if (t[u].l >= l && t[u].r <= r) {
        return opt == 1 ? t[u].sum : t[u].len - t[u].sum;
    } else {
        push_down(u);
        int mid = (t[u].l + t[u].r) >> 1;
        int s = 0;
        if (mid >= l) {
            s += query(u << 1, l, r, opt);
        }
        if (mid < r) {
            s += query(u << 1 | 1, l, r, opt);
        }
        return s;
    }
}

void modify2(int l0, int r0, int l1, int r1) {
    int x = query(1, l0, r0, 1);
    if (x == 0) {
        return;
    }
    modify(1, l0, r0, 0);
    int l = l1;
    int r = r1;
    int ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (query(1, l1, mid, 0) <= x) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    modify(1, l1, ans, 1);
}

int query2(int u, int l, int r) {
    if (t[u].l >= l && t[u].r <= r) {
        return t[u].ans;
    }
    push_down(u);
    int s = 0;
    int mid = (t[u].l + t[u].r) >> 1;
    if (mid >= l) {
        s = max(s, query2(u << 1, l, r));
    }
    if (mid < r) {
        s = max(s, query2(u << 1 | 1, l, r));
    }
    return max(s, min(t[u << 1].rmax, t[u << 1 | 1].l - l) + min(t[u << 1 | 1].lmax, r - t[u << 1].r));
}

void best_coder() {
    int n, m;
    cin >> n >> m;
    build(1,1,n);
    while(m--){
        int opt;
        cin >> opt;
        if(opt == 0) {
            int l, r;
            cin >> l >> r;
            modify(1, l, r, 0);
        } else if (opt == 1) {
            int l0, r0, l1, r1;
            cin >> l0 >> r0 >> l1 >> r1;
            modify2(l0, r0, l1, r1);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query2(1, l, r) << '\n';
        }
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}