P4344 75pts TLE 线段树 求调

关键是后面的点跑的飞快，前面的点反而 TLE。

// Author : hejinming2012
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define dbg(x) cout << #x " = " << (x) << endl
#define quickio ios::sync_with_stdio(false);
#define quickin cin.tie(0);
#define quickout cout.tie(0);
#define maxn 200005
using namespace std;
inline int read() {
    int now = 0, nev = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') nev = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { now = (now << 1) + (now << 3) + (c & 15); c = getchar(); }
    return now * nev;
}
void write(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
struct node {
    int l, r;
    int tot;
    int maxz;
    int lz, rz;
    int tag;
} t[maxn << 2];
int n;
void build(int idx, int l, int r) {
    t[idx].l = l;
    t[idx].r = r;
    t[idx].tag = -1;
    if (l == r) {
        t[idx].tot = 1;
        t[idx].maxz = 0;
        t[idx].lz = 0;
        t[idx].rz = 0;
        return;
    }
    int mid = l + r >> 1;
    build(idx << 1, l, mid);
    build(idx << 1 | 1, mid + 1, r);
    t[idx].tot = t[idx << 1].tot + t[idx << 1 | 1].tot;
    t[idx].maxz = 0;
    t[idx].lz = 0;
    t[idx].rz = 0;
}
void push_down(int idx) {
    if(t[idx].tag != -1) {
        int val = t[idx].tag;
        int l = idx << 1;
        int r = idx << 1 | 1;
        t[l].tag = val;
        t[r].tag = val;
        if(val == 0) {
            t[l].tot = 0;
            t[r].tot = 0;
            int lenl = t[l].r - t[l].l + 1;
            int lenr = t[r].r - t[r].l + 1;
            t[l].maxz = lenl;
            t[l].lz = lenl;
            t[l].rz = lenl;
            t[r].maxz = lenr;
            t[r].lz = lenr;
            t[r].rz = lenr;
        } else if(val == 1) {
            int lenl = t[l].r - t[l].l + 1;
            int lenr = t[r].r - t[r].l + 1;
            t[l].tot = lenl;
            t[r].tot = lenr;
            t[l].maxz = 0;
            t[r].maxz = 0;
            t[l].lz = 0;
            t[l].rz = 0;
            t[r].lz = 0;
            t[r].rz = 0;
        }
        t[idx].tag = -1;
    }
    return ;
}
void push_up(int idx) {
    int l = idx << 1;
    int r = idx << 1 | 1;
    t[idx].tot = t[l].tot + t[r].tot;
    t[idx].lz = t[l].lz;
    if(t[l].lz == t[l].r - t[l].l + 1)
        t[idx].lz += t[r].lz;
    t[idx].rz = t[r].rz;
    if(t[r].rz == t[r].r - t[r].l +1)
        t[idx].rz += t[l].rz;
    t[idx].maxz = max(t[l].maxz, t[r].maxz);
    t[idx].maxz = max(t[idx].maxz, t[l].rz + t[r].lz);
    return ;
}
void update_range(int idx, int l, int r, int val) {
    if(t[idx].l > r || t[idx].r < l) return ;
    if(t[idx].l >= l && t[idx].r <= r) {
        if(val == 0) {
            t[idx].tot = 0;
            int len = t[idx].r - t[idx].l + 1;
            t[idx].maxz = len;
            t[idx].lz = len;
            t[idx].rz = len;
            t[idx].tag = 0;
        } else if(val == 1) {
            int len = t[idx].r - t[idx].l + 1;
            t[idx].tot = len;
            t[idx].maxz = 0;
            t[idx].lz = 0;
            t[idx].rz = 0;
            t[idx].tag = 1;
        }
        return ;
    }
    push_down(idx);
    update_range(idx << 1, l, r, val);
    update_range(idx << 1 | 1, l, r, val);
    push_up(idx);
    return ;
}
int query_ones(int idx, int l, int r) {
    if(t[idx].l > r || t[idx].r < l)
        return 0;
    if(t[idx].l >= l && t[idx].r <= r)
        return t[idx].tot;
    push_down(idx);
    int lres = query_ones(idx << 1, l, r);
    int rres = query_ones(idx << 1 | 1, l, r);
    return lres + rres;
}
struct Query {
    int tot;
    int maxz;
    int lz, rz;
} query;
Query ask_assistant(int idx, int l, int r) {
    if(t[idx].l > r || t[idx].r < l)
        return Query{0, 0, 0, 0};
    if(t[idx].l >= l && t[idx].r <= r)
        return Query{t[idx].tot, t[idx].maxz, t[idx].lz, t[idx].rz};
    push_down(idx);
    Query lres = ask_assistant(idx << 1, l, r);
    Query rres = ask_assistant(idx << 1 | 1, l, r);
    if(lres.maxz == 0 && rres.maxz == 0 && lres.rz + rres.lz == 0)
        return Query{lres.tot + rres.tot, 0, lres.lz, rres.rz};
    Query res;
    res.tot = lres.tot + rres.tot;
    res.lz = lres.lz;
    if(lres.lz == t[idx << 1].r - t[idx << 1].l + 1)
        res.lz += rres.lz;
    res.rz = rres.rz;
    if(rres.rz == t[idx << 1 | 1].r - t[idx << 1 | 1].l + 1)
        res.rz += lres.rz;
    res.maxz = max(lres.maxz, rres.maxz);
    res.maxz = max(res.maxz, lres.rz + rres.lz);
    return res;
}
int ask(int idx, int l, int r) {
    Query res = ask_assistant(idx, l, r);
    return res.maxz;
}
int modify(int idx, int l, int r, int &k) {
    if(k <= 0 || t[idx].maxz == 0 || t[idx].l > r || t[idx].r < l)
        return 0;
    if(t[idx].l == t[idx].r) {
        if(t[idx].tot == 0 && k > 0) {
            update_range(idx, t[idx].l, t[idx].r, 1);
            k--;
        }
        return 0;
    }
    push_down(idx);
    modify(idx << 1, l, r, k);
    modify(idx << 1 | 1, l, r, k);
    push_up(idx);
    return 0;
}
signed main() {
    quickio
    quickin
    quickout
    int m;
    // n = read();
    // m = read();
    cin >> n >> m;
    build(1, 1, n);
    while(m--) {
        int op;
        // op = read();
        cin >> op;
        if(op == 0) {
            int l, r;
            // l = read(), r = read();
            cin >> l >> r;
            update_range(1, l, r, 0);
        } else if(op == 1) {
            int l0, r0, l1, r1;
            // l0 = read(), r0 = read();
            // l1 = read(), r1 = read();
            cin >> l0 >> r0 >> l1 >> r1;
            int ones = query_ones(1, l0, r0);
            update_range(1, l0, r0, 0);
            int k = ones;
            modify(1, l1, r1, k);
        } else if(op == 2) {
            int l, r;
            // l = read(), r = read();
            cin >> l >> r;
            int ans = ask(1, l, r);
            // write(ans), putchar(10);
            cout << ans << endl;
        }
    }
    return 0;
}