rmpq

pystraf11 · 2026-04-26 17:34:24 · 题解

Description

给定平面，每个点 (x,y) 有权值 w(x,y)，n 次操作分两种：

操作强制在线。其中 w(x,y) 为含幺半群 D，有运算 D\times D，有结合律但无交换律。

Limitations

最多使用 2\times 10^7 次运算。

Solution

维护划分，则 B 次操作会把 x,y 轴分别划成 O(B) 段，把平面划成 O(B^2) 格矩形，并且每格内 w(x,y) 相同可以直接存。考虑合并两个结构，把 x,y 轴的划分点归并起来，容易把格子对应到新划分上，直接合并出新的 w。

由于强制在线，考虑二进制分组，\text{update} 时新建一个划分，不断合并直到大小超过 B，那么只会出现 O(\frac{n}{B}) 个划分，\text{query} 时在每个划分上二分定位并合并即可。取 B=O(\sqrt n)，运算次数 O(n\sqrt n)。

由于要二分，复杂度多一个 \log B，可以分散层叠优化掉，不过没必要。

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

// Header
struct Data {
    unsigned short a, b, c, d;
    void operator*=(const Data &x);
    void clr();
};

constexpr int inf = 2e9, B = 256;
struct Grid {
    int n, m;
    vector<int> X, Y;
    vector<Data> dat;

    Grid() {}
    Grid(int x, int dim, const Data& d1, const Data& d2) {
        if (dim) {
            resize(1, 2);
            Y[0] = x, X[0] = Y[1] = inf;
        }
        else {
            resize(2, 1);
            X[0] = x, X[1] = Y[0] = inf;
        }
        dat[0] = d1, dat[1] = d2;
    }

    void resize(int _n, int _m) {
        n = _n, m = _m;
        X.resize(n);
        Y.resize(m);
        Data e; e.clr();
        dat.resize(n * m, e);
    }

    int size() { return max(0, n + m - 2); }
    Data get(int x, int y) const { return dat[x * m + y]; }
    void set(int x, int y, const Data& d) { dat[x * m + y] = d; }

    Data query(int x, int y) {
        return get(upper_bound(X.begin(), X.end(), x) - X.begin(),
                   upper_bound(Y.begin(), Y.end(), y) - Y.begin());
    }
};

using pii = pair<int, int>;
array<pii, B + 5> p, q;

Grid operator+(const Grid& a, const Grid& b) {
    Grid res;
    res.resize(a.n + b.n - 1, a.m + b.m - 1);

    int j = 0, k = 0;
    for (int i = 0; i < a.n; i++) {
        while (j < b.n && b.X[j] < a.X[i]) {
            p[k] = pii(i, j);
            res.X[k] = b.X[j];
            j++, k++;
        }
        p[k] = pii(i, j);
        res.X[k] = a.X[i];
        k++; 
    }

    j = 0, k = 0;
    for (int i = 0; i < a.m; i++) {
        while (j < b.m && b.Y[j] < a.Y[i]) {
            q[k] = pii(i, j);
            res.Y[k] = b.Y[j];
            j++, k++;
        }
        q[k] = pii(i, j);
        res.Y[k] = a.Y[i];
        k++;
    }

    for (int i = 0; i < res.n; i++)
        for (int j = 0; j < res.m; j++) {
            Data tmp = a.get(p[i].first, q[j].first);
            tmp *= b.get(p[i].second, q[j].second);
            res.set(i, j, tmp);
        }
    return res;
}

vector<Grid> grid;
int siz = 0;

void update(int x, int dim, Data d1, Data d2) {
    grid.emplace_back(x, dim, d1, d2);
    siz++;
    while (siz > 1 && grid[siz - 1].size() < B && 
           grid[siz - 2].size() <= grid[siz - 1].size()) {

        grid[siz - 2] = grid[siz - 2] + grid[siz - 1];
        siz--;
        grid.pop_back();
    }
}

Data query(int x, int y) {
    Data res;
    res.clr();
    for (int i = 0; i < siz; i++) res *= grid[i].query(x, y);
    return res;
}

::::