题目传送门
0x00
习题课上怒敲1.5h然后没过
感谢好心的DS大佬Elysia11帮忙改了1h代码！！
0x01
前两个操作都是很简单，难点在于第三个撤销操作
正着操作很难，因为可能后面一个撤销前面所有操作直接无效，所以考虑倒序，优先处理操作3,（很常见的一个思路：正难则反）
考虑维护一棵线段树，再开一个判断操作是否无效的数组，如果有操作3，则将操作3的区间\([l_i,r_i]\)全部打上标记1，在进行操作1、2时判断一下标记是否为1，如果是就直接不操作了。
在维护线段树时可以直接动态开点,复杂度\(O(mlogv)\)，也可以用离散化优雅一下，复杂度\(O(mlogm)\)
然后就是正常的线段树了，复杂度\(O(nlogn)\)
0x02 Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
//using ll = long long;
const int MAXN = 5e5 + 10;
const ll INF = 1e18;
long long lowbit(long long x){return x&-x;
}
struct Op {int op, id;ll t;int l, r;ll k;bool operator<(const Op& a)const{if(t!=a.t){return t<a.t;}else if(t==a.t){return id<a.id;}}
};
struct SegNode {ll v, lz;
};
int n, m;
ll a[MAXN];
Op ops[MAXN];
ll ans[MAXN];
int cnt = 0;
int length = 0;
SegNode seg[MAXN * 4];
void build(int node, int l, int r) {seg[node].lz = 0;if (l == r) {seg[node].v = a[l];return;}int mid = (l + r) / 2;build(node * 2, l, mid);build(node * 2 + 1, mid + 1, r);seg[node].v = max(seg[node * 2].v, seg[node * 2 + 1].v);
}
void pd(int node) {if (seg[node].lz != 0) {seg[node * 2].v += seg[node].lz;seg[node * 2].lz += seg[node].lz;seg[node * 2 + 1].v += seg[node].lz;seg[node * 2 + 1].lz += seg[node].lz;seg[node].lz = 0;}
}
void upd(int node, int l, int r, int ql, int qr, ll k) {if (ql <= l && r <= qr) {seg[node].v += k;seg[node].lz += k;return;}pd(node);int mid = (l + r) / 2;if (ql <= mid) {upd(node * 2, l, mid, ql, qr, k);}if (qr > mid) {upd(node * 2 + 1, mid + 1, r, ql, qr, k);}seg[node].v = max(seg[node * 2].v, seg[node * 2 + 1].v);
}
ll qry(int node, int l, int r, int ql, int qr) {if (ql <= l && r <= qr) {return seg[node].v;}pd(node);int mid = (l + r) / 2;ll res = -INF;if (ql <= mid) {res = max(res, qry(node * 2, l, mid, ql, qr));}if (qr > mid) {res = max(res, qry(node * 2 + 1, mid + 1, r, ql, qr));}return res;
}
long long ts[11451411];
int sz;
int get(ll t) {return lower_bound(ts+1, ts+sz+1, t) - ts;
}
int diff[11451411];
void add1(long long x,long long v){while(x<=length){diff[x]+=v;x+=lowbit(x);}
}
void add2(long long l,long long r,long long v){add1(l,v);add1(r+1,-v);
}
long long getsum(long long x){long long ans=0;while(x){ans+=diff[x];x-=lowbit(x);}return ans;
}
int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= m; ++i) {cin >> ops[i].op;if (ops[i].op == 1) {cin >> ops[i].t >> ops[i].l >> ops[i].r >> ops[i].k;} else if(ops[i].op == 2){cin >> ops[i].t >> ops[i].l >> ops[i].r;ops[i].k = 0;} else if(ops[i].op == 3){cin >> ops[i].t >> ops[i].l >> ops[i].r;ops[i].k = 0;ts[++length]=ops[i].l;ts[++length]=ops[i].r;}ops[i].id = i;ts[++length]=ops[i].t;}sort(ops+1,ops+m+1);sort(ts+1,ts+length+1);sz = unique(ts+1,ts+length+1)-ts-1;for (int i = m ; i >= 0; --i) {if (!getsum(get(ops[i].t))&&ops[i].op == 3) {ll L_time = ops[i].l;ll R_time = ops[i].r;int l = get(L_time);int r = get(R_time);add2(l,r,1);}}ll sum = 0;build(1, 1, n);for (int i = 1; i <= m; ++i) {int tid = get(ops[i].t);if (!getsum(get(ops[i].t)) && ops[i].op == 1) {upd(1, 1, n, ops[i].l, ops[i].r, ops[i].k);} else if(!getsum(get(ops[i].t)) && ops[i].op == 2) {ans[cnt++] = qry(1, 1, n, ops[i].l, ops[i].r);}}cout << cnt << "\n";for (int i = 0; i < cnt; ++i) {cout << ans[i] << "\n";}return 0;
}
最后看一眼我的抽象\(70pts\)代码（再次膜拜DS大佬Elysia11！！）
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e5 + 10;
const ll INF = 1e18;
struct Op {int op, id;ll t;int l, r;ll k;
};
struct SegNode {ll v, lz;
};
int n, m;
ll a[MAXN];
Op ops[MAXN];
ll ans[MAXN];
int cnt = 0;
SegNode seg[MAXN * 4];
void build(int node, int l, int r) {seg[node].lz = 0;if (l == r) {seg[node].v = a[l];return;}int mid = (l + r) / 2;build(node * 2, l, mid);build(node * 2 + 1, mid + 1, r);seg[node].v = max(seg[node * 2].v, seg[node * 2 + 1].v);
}
void pd(int node) {if (seg[node].lz != 0) {seg[node * 2].v += seg[node].lz;seg[node * 2].lz += seg[node].lz;seg[node * 2 + 1].v += seg[node].lz;seg[node * 2 + 1].lz += seg[node].lz;seg[node].lz = 0;}
}
void upd(int node, int l, int r, int ql, int qr, ll k) {if (ql <= l && r <= qr) {seg[node].v += k;seg[node].lz += k;return;}pd(node);int mid = (l + r) / 2;if (ql <= mid) {upd(node * 2, l, mid, ql, qr, k);}if (qr > mid) {upd(node * 2 + 1, mid + 1, r, ql, qr, k);}seg[node].v = max(seg[node * 2].v, seg[node * 2 + 1].v);
}
ll qry(int node, int l, int r, int ql, int qr) {if (ql <= l && r <= qr) {return seg[node].v;}pd(node);int mid = (l + r) / 2;ll res = -INF;if (ql <= mid) {res = max(res, qry(node * 2, l, mid, ql, qr));}if (qr > mid) {res = max(res, qry(node * 2 + 1, mid + 1, r, ql, qr));}return res;
}
int get(const vector<ll>& ts, ll t) {return lower_bound(ts.begin(), ts.end(), t) - ts.begin();
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];}vector<ll> ts;for (int i = 0; i < m; ++i) {cin >> ops[i].op;if (ops[i].op == 1) {cin >> ops[i].t >> ops[i].l >> ops[i].r >> ops[i].k;} else {cin >> ops[i].t >> ops[i].l >> ops[i].r;ops[i].k = 0;}ops[i].id = i;ts.push_back(ops[i].t);}sort(ts.begin(), ts.end());ts.erase(unique(ts.begin(), ts.end()), ts.end());int sz = ts.size();vector<ll> diff(sz + 2, 0);for (int i = m - 1; i >= 0; --i) {if (ops[i].op == 3) {ll L_time = ops[i].l;ll R_time = ops[i].r;int l = get(ts, L_time);int r = upper_bound(ts.begin(), ts.end(), R_time) - ts.begin() - 1;if (l <= r) {diff[l]++;diff[r + 1]--;}}}vector<bool> valid(sz, true);ll sum = 0;for (int i = 0; i < sz; ++i) {sum += diff[i];if (sum > 0) {valid[i] = false;}}build(1, 1, n);vector<pair<ll, int>> ops2;for (int i = 0; i < m; ++i) {int tid = get(ts, ops[i].t);if (valid[tid] && ops[i].op != 3) {ops2.emplace_back(ops[i].t, ops[i].id);}}sort(ops2.begin(), ops2.end(), [&](const pair<ll, int>& a, const pair<ll, int>& b) {if (a.first != b.first) {return a.first < b.first;}return a.second < b.second;});for (auto& p : ops2) {int i = p.second;if (ops[i].op == 1) {upd(1, 1, n, ops[i].l, ops[i].r, ops[i].k);} else if (ops[i].op == 2) {ans[cnt++] = qry(1, 1, n, ops[i].l, ops[i].r);}}cout << cnt << "\n";for (int i = 0; i < cnt; ++i) {cout << ans[i] << "\n";}return 0;
}