P14152 题解

省流：P10374 + 弱化版的 P1253。

容易发现如果没有撤销操作的话该题就是 P1253 的弱化版（没有区间推平）。

所以考虑撤销操作怎么做。

输入格式里面说

l_i \le r_i < t_i

，说明撤销的只能是自己前面的操作。

所以我们结算的时候就应该按时间顺序从后往前结算撤销操作。下面的内容默认已经将操作按时间顺序排序。

然后这里结算的时候就是 P10374 的一个大概过程，可以用差分维护每个操作是否被撤销。

具体地，可以二分出来每次成功的撤销操作的撤销区间是从第几个操作到第几个操作，然后区间加

1

。

如果某个操作的对应的值是

0

，就代表这次操作最后是成功的。

最后你把成功的非撤销操作再拎出来结算一遍就行了，这里可以直接参考 P1253。

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 55;
int n, m, a[N], cnt, b[N];
struct node { int id, opt, t, l, r, k; } q1[N], q2[N];
bool cmp(node n1, node n2) {
    if (n1.t == n2.t) return n1.id < n2.id;
    return n1.t < n2.t;
}
struct SegTree {
    int mx[N << 4], tag[N << 4];
    #define L (O << 1)
    #define R (O << 1 | 1)
    #define M ((st + en) >> 1)
    void build(int O, int st, int en) {
        tag[O] = 0; if (st == en) mx[O] = a[st];
        else build(L, st, M), build(R, M + 1, en), mx[O] = max(mx[L], mx[R]);
    }
    void spread(int O, int st, int en) {
        if (tag[O] == 0) return;
        mx[L] += tag[O], mx[R] += tag[O];
        tag[L] += tag[O], tag[R] += tag[O], tag[O] = 0;
    }
    void update(int O, int st, int en, int l, int r, int k) {
        if (l <= st && en <= r) mx[O] += k, tag[O] += k;
        else {
            spread(O, st, en);
            if (l <= M) update(L, st, M, l, r, k);
            if (r > M) update(R, M + 1, en, l, r, k);
            mx[O] = max(mx[L], mx[R]);
        }
    }
    int query(int O, int st, int en, int l, int r) {
        if (l <= st && en <= r) return mx[O];
        spread(O, st, en); int o = -1e18;
        if (l <= M) o = max(o, query(L, st, M, l, r));
        if (r > M) o = max(o, query(R, M + 1, en, l, r));
        return o;
    }
} T;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    for (int i = 1;i <= m;i++) {
        q1[i].id = i;
        cin >> q1[i].opt >> q1[i].t >> q1[i].l >> q1[i].r;
        if (q1[i].opt == 1) cin >> q1[i].k;
    }
    sort(q1 + 1, q1 + 1 + m, cmp);
    for (int i = m;i >= 1;i--) {
        b[i] += b[i + 1];
        if (q1[i].opt == 3 && b[i] == 0) {
            int l = 1, r = n, sl = 0, sr = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (q1[mid].t >= q1[i].l) sl = mid, r = mid - 1;
                else l = mid + 1;
            }
            l = 1, r = n;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (q1[mid].t <= q1[i].r) sr = mid, l = mid + 1;
                else r = mid - 1;
            }
            b[sr]++, b[sl - 1]--;
        } else if (b[i] == 0) q2[++cnt] = q1[i];
    }
    T.build(1, 1, n);
    vector<int> v;
    for (int i = cnt;i >= 1;i--) {
        if (q2[i].opt == 1) T.update(1, 1, n, q2[i].l, q2[i].r, q2[i].k);
        else v.push_back(T.query(1, 1, n, q2[i].l, q2[i].r));
    }
    cout << v.size() << "\n";
    for (auto u : v) cout << u << "\n";
    return 0;
}

文章操作

相关推荐

评论

P14152 题解