TB5x

pystraf11 · 2026-04-23 21:40:21 · 题解

Description

最多使用 10^8 次运算。

Solution

对 操作 分块，设块长为 B，逐块处理。每块内的操作会把 x,y 轴分别划成 O(B) 段，把平面划成 O(B^2) 块矩形。从下往上建出线段树，每个节点存 x,y 轴的所有划分点 (p_i,p^\prime_i) 表示 p_i 平移到 p^\prime_i，pushup 时双指针合并。另外还要维护一棵线段树来存 (D,O)，初始为 n 个叶子节点。将每块矩形内的点权在值线段树上合并。

在划分的线段树上，从上往下做分治，传递 \text{id}_{a,b} 表示 (a,b) 矩形在值线段树上的根。递归到叶子时执行操作，对于每个节点，先把左子树按 p^\prime_i 排序，把当前矩形的线段树节点合并到左子树划分的矩形内，递归左子树。

然后处理左子树对坐标的影响，\text{id} 需要重排，并求出左子树变换后的 p_i，最后合并节点到右子树并递归下去。注意递归完一边后，要把值线段树上的新节点下传并销毁掉，这样才能保证标记推到叶节点。显然分治时每层是 O(\text{len}^2) 的，主定理可得总共为 O(B^2)。取 B=\sqrt n 得复杂度 O(q\sqrt n)，注意卡常数。

::::info[code]

#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;
}

class Data {
    friend class Operation;
    friend int main();
private:
    unsigned int x, sz, T, flag;
    void read();
    void print() const;
public:
    Data() { clr(); }
    void add_eq(const Data &a);
    void add(const Data &a, const Data &b);
    void clr();
    bool empty() const;
};

class Operation {
    friend int main();
private:
    unsigned int a, b, L, R, flag;
    void read();
public:
    Operation() { clr(); }
    void apply(Data &w) const;
    void apply(Operation &w) const;
    void clr();
    bool empty() const;
};

constexpr int S = 150;
using pii = pair<int, int>;

// segment tree node
struct Node {
    Data val; Operation tag; int s[2];
    void f(const Operation &w) { w.apply(val), w.apply(tag); }
};

// stable_sort is faster
void solve(const int n, const int m, const int p[], const Data d[],
           const int x1[], const int x2[], const int y1[], const int y2[],
           const Operation o[][3][3], Data ans[][3][3]) {
    vector<int> _p(n), _q(p, p + n); iota(_p.begin(), _p.end(), 0);
    vector<Node> s(n * 20); int tot = 0;
    for (int i = 0; i < n; i++) s[tot++] = Node{d[i], Operation(), {-1, -1}};

    // merge two nodes
    auto merge = [&](int u, int v) {
        if (u == -1 || v == -1) return max(u, v);
        Data w; w.add(s[u].val, s[v].val);
        s[tot++] = Node{w, Operation(), {u, v}};
        return tot - 1;
    };

    vector<vector<pii>> X, Y; vector<int> L, R, mapx, mapy;
    auto solve = [&](int l, int r) {
        X.clear(), Y.clear(), L.clear(), R.clear();
        // Merge two class P, Q to res.
        auto comp = [&](vector<pii>& P, vector<pii>& Q, vector<pii>& res) {
            vector<pii> T;
            for (auto [px, py] : P) T.emplace_back(py, px);
            stable_sort(T.begin(), T.end()), res = {{0, 0}};
            auto itt = T.begin() + 1, itq = Q.begin() + 1;
            int lst = 0, lt = T[0].second, lq = Q[0].second;
            while (itt < T.end() - 1 || itq < Q.end() - 1) {
                if (itt < T.end() - 1 && (itq == Q.end() - 1 || itt->first < itq->first)) {
                    int len = itt->first - lst;
                    if (len > 0) res.emplace_back(itt->second, lq + len);
                    else res.back().first = itt->second;
                    lt = itt->second, lq += len, lst += len, itt++;
                } else {
                    int len = itq->first - lst;
                    if (len > 0) res.emplace_back(lt + len, itq->second);
                    else res.back().second = itq->second;
                    lt += len, lq = itq->second, lst += len, itq++;
                }
            }
            stable_sort(res.begin(), res.end());
            res.emplace_back(n, n);
        };

        // build segment tree.
        auto prep = [&](auto &&self, int l, int r) -> int {
            int u = X.size();
            X.emplace_back(), Y.emplace_back();
            L.emplace_back(-1), R.emplace_back(-1);
            if (l == r) {
                X[u] = {{0, 0}, {x1[l], x1[l] + n - x2[l]}, {x2[l], x1[l]}, {n, n}};
                Y[u] = {{0, 0}, {y1[l], y1[l] + n - y2[l]}, {y2[l], y1[l]}, {n, n}};
            }
            else {
                int mid = (l + r) / 2;
                int ls = self(self, l, mid), rs = self(self, mid + 1, r);
                comp(X[ls], X[rs], X[u]), comp(Y[ls], Y[rs], Y[u]);
                L[u] = ls, R[u] = rs;
            }
            return u;
        };
        prep(prep, l, r);

        // revoke.
        auto commit = [&](int sz) {
            while (tot > sz) {
                tot--;
                for (int i = 0; i < 2; i++) {
                    int v = s[tot].s[i];
                    if (v < n) s[tot].tag.apply(s[v].val);
                    else s[v].f(s[tot].tag);
                }
            }
        };

        // process on the segment tree
        auto proc = [&](auto &&self, int u, int l, int r, vector<vector<int>> id) -> void {
            if (l == r) {
                // answers are on leaf nodes.
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (id[i][j] == -1) ans[l][i][j].clr();
                        else {
                            ans[l][i][j] = s[id[i][j]].val;
                            s[id[i][j]].f(o[l][i][j]);
                        }
                    }
                }
                return;
            }

            // reorder by id.
            int mid = (l + r) / 2, ls = L[u], rs = R[u];
            vector<int> ordx(X[ls].size() - 1), ordy(Y[ls].size() - 1), _x = ordx, _y = ordy;
            iota(ordx.begin(), ordx.end(), 0), iota(ordy.begin(), ordy.end(), 0);
            stable_sort(ordx.begin(), ordx.end(), [&](int a, int b) { return X[ls][a].second < X[ls][b].second; });
            stable_sort(ordy.begin(), ordy.end(), [&](int a, int b) { return Y[ls][a].second < Y[ls][b].second; });
            for (int i = 0; i < int(ordx.size()); i++) _x[ordx[i]] = i;
            for (int i = 0; i < int(ordy.size()); i++) _y[ordy[i]] = i;

            // mapping to left.
            int sz = tot;
            vector<int> px(X[ls].size()), py(Y[ls].size()), sx = px, sy = py, tx(X[rs].size()), ty(Y[rs].size());
            for (int i = 0; i < int(X[ls].size()); i++) {
                px[i] = lower_bound(X[u].begin(), X[u].end(), X[ls][i].first,
                                    [&](pii ele, int val) { return ele.first < val; }) - X[u].begin();
            }
            for (int i = 0; i < int(Y[ls].size()); i++) {
                py[i] = lower_bound(Y[u].begin(), Y[u].end(), Y[ls][i].first,
                                    [&](pii ele, int val) { return ele.first < val; }) - Y[u].begin();
            }
            for (int i = 0; i < int(X[ls].size()) - 1; i++) sx[i + 1] = sx[i] + px[ordx[i] + 1] - px[ordx[i]];
            for (int i = 0; i < int(Y[ls].size()) - 1; i++) sy[i + 1] = sy[i] + py[ordy[i] + 1] - py[ordy[i]];

            // build class of right & mapping.
            vector<int> _X, _Y;
            auto itx = X[ls].begin(), ity = Y[ls].begin();
            for (auto [p, q] : X[u]) {
                if ((itx + 1)->first == p) itx++;
                _X.emplace_back(p - itx->first + itx->second);
            }
            for (auto [p, q] : Y[u]) {
                if ((ity + 1)->first == p) ity++;
                _Y.emplace_back(p - ity->first + ity->second);
            }
            stable_sort(_X.begin(), _X.end()), stable_sort(_Y.begin(), _Y.end());
            for (int i = 0; i < int(X[rs].size()); i++) tx[i] = lower_bound(_X.begin(), _X.end(), X[rs][i].first) - _X.begin();
            for (int i = 0; i < int(Y[rs].size()); i++) ty[i] = lower_bound(_Y.begin(), _Y.end(), Y[rs][i].first) - _Y.begin();

            // left
            {
                // id of left.
                vector tmp(X[ls].size() - 1, vector<int>(Y[ls].size() - 1, -1));
                for (int i = 0; i < int(X[ls].size()) - 1; i++) {
                    for (int j = 0; j < int(Y[ls].size()) - 1; j++) {
                        for (int p = px[i]; p < px[i + 1]; p++) {
                            for (int q = py[j]; q < py[j + 1]; q++) tmp[i][j] = merge(tmp[i][j], id[p][q]);
                        }
                    }
                }
                self(self, ls, l, mid, tmp), commit(sz);
                // reorder.
                auto swp = id;
                for (int i = 0; i < int(X[ls].size()) - 1; i++) {
                    for (int j = 0; j < int(Y[ls].size()) - 1; j++) {
                        int ip = ordx[i], jp = ordy[j];
                        for (int p = 0; p < px[ip + 1] - px[ip]; p++) {
                            for (int q = 0; q < py[jp + 1] - py[jp]; q++) swp[sx[i] + p][sy[j] + q] = id[px[ip] + p][py[jp] + q];
                        }
                    }
                }
                id = swp;
            }

            {
                // id of right.
                vector tmp(X[rs].size() - 1, vector<int>(Y[rs].size() - 1, -1));
                for (int i = 0; i < int(X[rs].size()) - 1; i++) {
                    for (int j = 0; j < int(Y[rs].size()) - 1; j++) {
                        for (int p = tx[i]; p < tx[i + 1]; p++) {
                            for (int q = ty[j]; q < ty[j + 1]; q++) tmp[i][j] = merge(tmp[i][j], id[p][q]);
                        }
                    }
                }
                self(self, rs, mid + 1, r, tmp), commit(sz);
            }
        };

        // build id of root
        vector id(X[0].size() - 1, vector<int>(Y[0].size() - 1, -1));
        mapx.assign(n, 0), mapy.assign(n, 0);   // belong
        for (int i = 0; i < int(X[0].size()) - 1; i++) {
            for (int j = X[0][i].first; j < X[0][i + 1].first; j++) mapx[j] = i;
        }
        for (int i = 0; i < int(Y[0].size()) - 1; i++) {
            for (int j = Y[0][i].first; j < Y[0][i + 1].first; j++) mapy[j] = i;
        }
        for (int i = 0; i < n; i++) {
            int xid = mapx[_p[i]], yid = mapy[_q[i]];
            id[xid][yid] = merge(id[xid][yid], i);
        }
        proc(proc, 0, l, r, id);   // solve

        commit(n);
        // mapping.
        for (int i = 0; i < int(X[0].size()) - 1; i++) {
            for (int j = X[0][i].first; j < X[0][i + 1].first; j++) mapx[j] = j - X[0][i].first + X[0][i].second;
        }
        for (int i = 0; i < int(Y[0].size()) - 1; i++) {
            for (int j = Y[0][i].first; j < Y[0][i + 1].first; j++) mapy[j] = j - Y[0][i].first + Y[0][i].second;
        }
        for (int i = 0; i < n; i++) _p[i] = mapx[_p[i]], _q[i] = mapy[_q[i]];
    };

    // process each block.
    for (int i = 0; i < m; i += S) solve(i, min(m, i + S) - 1);
}