LG P3710 方方方的数据结构 Solution

Description

有一个长度为 $n$ 的序列 $a$，初始全为 $0$，执行 $q$ 次操作分四种：

• 1 l r x：对每个 $l\le i\le r$ 执行 $a_i\leftarrow a_i+x$.
• 2 l r x：对每个 $l\le i\le r$ 执行 $a_i\leftarrow a_i\times x$.
• 3 i：求 $a_i\mathrm{mod}998244353$.
• 4 k：撤销第 $k$ 次操作，保证为修改操作.

Limitations

$1\le n,q\le 1.5\times 10^5$
$1\le l\le r\le n$
$1\le i\le n,1\le k\le q$
$1\le x\le 1073741823$
$4.5\text{s},125\text{MB}$
保证数据随机.

Solution

假如没有 4 操作就是板子.
但有了 4 操作后，我们不好计算撤销操作对 $a$ 的影响.

将操作全部离线下来，那么可以确定每个修改操作存在的时间范围.
考虑加上时间维，构成二维平面，那么每次修改就是矩形加/乘，查询就是单点查.

由于这个平面很大，需要用 KDT 维护，并将标记永久化.
时间复杂度 $O(q\sqrt{n})$，不需要数据随机.

Code

$5.87\text{KB},2.76\text{s},7.43\text{MB}\text{(c++20 with o2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}constexpr int mod = 998244353;class KDT {
private:struct Node {int x, y;i64 val;i64 add, mul;int xmin, xmax, ymin, ymax;Node *ls, *rs;Node(int x, int y) : x(x), y(y), val(0), add(0), mul(1),xmin(x), xmax(x), ymin(y), ymax(y),ls(nullptr), rs(nullptr) {}};Node* rt;void apply_add(Node* u, i64 v) {if (!u) return;u->val = (u->val + v) % mod;u->add = (u->add + v) % mod;}void apply_mul(Node* u, i64 v) {if (!u) return;u->val = (u->val * v) % mod;u->add = (u->add * v) % mod;u->mul = (u->mul * v) % mod;}void pushdown(Node* u) {if (!u) return;if (u->mul != 1) {apply_mul(u->ls, u->mul);apply_mul(u->rs, u->mul);u->mul = 1;}if (u->add != 0) {apply_add(u->ls, u->add);apply_add(u->rs, u->add);u->add = 0;}}void pushup(Node* u) {if (!u) return;u->xmin = u->xmax = u->x;u->ymin = u->ymax = u->y;if (u->ls) {u->xmin = min(u->xmin, u->ls->xmin);u->xmax = max(u->xmax, u->ls->xmax);u->ymin = min(u->ymin, u->ls->ymin);u->ymax = max(u->ymax, u->ls->ymax);}if (u->rs) {u->xmin = min(u->xmin, u->rs->xmin);u->xmax = max(u->xmax, u->rs->xmax);u->ymin = min(u->ymin, u->rs->ymin);u->ymax = max(u->ymax, u->rs->ymax);}}Node* build(vector<Node*>& nodes, int l, int r, int dep) {if (l >= r) return nullptr;int mid = (l + r) / 2;if (dep % 2 == 0) {nth_element(nodes.begin() + l, nodes.begin() + mid, nodes.begin() + r, [](Node* a, Node* b) { return a->x < b->x; });} else {nth_element(nodes.begin() + l, nodes.begin() + mid, nodes.begin() + r, [](Node* a, Node* b) { return a->y < b->y; });}Node* u = nodes[mid];u->ls = build(nodes, l, mid, dep + 1);u->rs = build(nodes, mid + 1, r, dep + 1);pushup(u);return u;}void rect_add(Node* u, int x1, int y1, int x2, int y2, i64 v) {if (!u) return;if (u->xmax < x1 || u->xmin > x2 || u->ymax < y1 || u->ymin > y2) return;if (x1 <= u->xmin && u->xmax <= x2 && y1 <= u->ymin && u->ymax <= y2) {apply_add(u, v);return;}pushdown(u);if (x1 <= u->x && u->x <= x2 && y1 <= u->y && u->y <= y2) u->val = (u->val + v) % mod;rect_add(u->ls, x1, y1, x2, y2, v);rect_add(u->rs, x1, y1, x2, y2, v);}void rect_mul(Node* u, int x1, int y1, int x2, int y2, i64 v) {if (!u) return;if (u->xmax < x1 || u->xmin > x2 || u->ymax < y1 || u->ymin > y2) return;if (x1 <= u->xmin && u->xmax <= x2 && y1 <= u->ymin && u->ymax <= y2) {apply_mul(u, v);return;}pushdown(u);if (x1 <= u->x && u->x <= x2 && y1 <= u->y && u->y <= y2) u->val = u->val * v % mod;rect_mul(u->ls, x1, y1, x2, y2, v);rect_mul(u->rs, x1, y1, x2, y2, v);}i64 point_query(Node* u, int x, int y, i64 tadd = 0, i64 tmul = 1) {if (!u) return 0;if (u->x == x && u->y == y) return (u->val * tmul + tadd) % mod;pushdown(u);bool go_left;if (u->ls && u->ls->xmin <= x && x <= u->ls->xmax && u->ls->ymin <= y && y <= u->ls->ymax) go_left = true;else if (u->rs && u->rs->xmin <= x && x <= u->rs->xmax && u->rs->ymin <= y && y <= u->rs->ymax) go_left = false;else return 0;if (go_left) return point_query(u->ls, x, y, (tadd + u->add * tmul) % mod, tmul * u->mul % mod);else return point_query(u->rs, x, y, (tadd + u->add * tmul) % mod, tmul * u->mul % mod);}public:KDT() : rt(nullptr) {}void rect_add(int x1, int y1, int x2, int y2, i64 v) {rect_add(rt, x1, y1, x2, y2, v);}void rect_mul(int x1, int y1, int x2, int y2, i64 v) {rect_mul(rt, x1, y1, x2, y2, v);}i64 point_query(int x, int y) {return point_query(rt, x, y);}void build(const vector<pair<int, int>>& points) {vector<Node*> nodes;for (auto& p : points) {nodes.push_back(new Node(p.first, p.second));}rt = build(nodes, 0, nodes.size(), 0);}
};struct modify {int x1, y1, x2, y2, t, v;inline modify() : modify(0, 0, 0, 0, 0, 0) {}inline modify(int x1, int y1, int x2, int y2, int t, int v): x1(x1), y1(y1), x2(x2), y2(y2), t(t), v(v) {}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, q;cin >> n >> q;KDT kdt;vector<pair<int, int>> pts;vector<modify> mdf(q);for (int i = 0, op, l, r, k; i < q; i++) {cin >> op;if (op <= 2) {cin >> l >> r >> k;l--, r--;mdf[i] = {l, i, r, q - 1, op, k};}if (op == 3) {cin >> k, k--;pts.emplace_back(k, i);}if (op == 4) {cin >> k, k--;mdf[k].y2 = i;}}kdt.build(pts);for (int i = 0; i < q; i++) {if (mdf[i].t == 1) kdt.rect_add(mdf[i].x1, mdf[i].y1, mdf[i].x2, mdf[i].y2, mdf[i].v);if (mdf[i].t == 2) kdt.rect_mul(mdf[i].x1, mdf[i].y1, mdf[i].x2, mdf[i].y2, mdf[i].v);}for (int i = 0; i < pts.size(); i++)cout << kdt.point_query(pts[i].first, pts[i].second) << '\n';return 0;
}