题解：Vera and Modern Art

算法思路

本题需要高效处理在无限大平面上的周期性染色和查询。关键在于利用二维差分 + 扫描线 + 树状数组的技巧，将问题转化为一维问题处理。

1. 问题分析

每次染色操作：

• 给定 $(x_i, y_i, v_i)$
• 计算 $a_i =$ 最大的不超过 $x_i$ 的 $2$ 的幂
• 计算 $b_i =$ 最大的不超过 $y_i$ 的 $2$ 的幂
• 染色点集：$(x_i + a_i p, y_i + b_i q)$，其中 $p, q \ge 0$

这实际上是在平面上以 $(x_i, y_i)$ 为起点，$a_i$ 为 $x$ 方向周期，$b_i$ 为 $y$ 方向周期的无限网格染色。

2. 关键转换

坐标变换

将坐标 $(x, y)$ 映射到新的坐标系：

• $x$ 的二进制表示逆序后作为新 $x$ 坐标
• $y$ 的二进制表示逆序后作为新 $y$ 坐标

这样，原来的周期性染色在新坐标系中变成矩形区域染色。

二维差分

对于每个染色操作 $(x, y, v)$ 在新坐标系中对应的矩形 $[lx, rx) \times [ly, ry)$，使用二维差分：

• $(lx, ly) + v$
• $(lx, ry) - v$
• $(rx, ly) - v$
• $(rx, ry) + v$

3. 算法步骤

1. 坐标转换：将原坐标转换为新坐标
2. 构建事件：将染色操作转为差分事件，查询操作转为查询事件
3. 扫描线：按 $x$ 坐标排序所有事件
4. 树状数组：维护当前 $x$ 位置对应的 $y$ 坐标上的值
5. 处理查询：遇到查询时在树状数组中查询对应 $y$ 位置的值

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e6 + 10, Mxlg = 61;
int n, Q;

// 二进制逆序
int rev(int Z) {
    int X = 0, H = 1ll << Mxlg;
    while (Z) {
        H >>= 1;
        if (Z & 1) X |= H;
        Z >>= 1;
    }
    return X;
}

// 坐标转换：返回新坐标系中的矩形范围
pair<int, int> cov(int x) {
    int d = __lg(x);           // 最高位位置
    x ^= (1ll << d);           // 去掉最高位
    x = rev(x);                // 剩余位逆序
    return {x + 1, x + (1ll << (Mxlg - d))};
}

struct node {
    int x, y, op, val;  // op=1:更新, op=2:查询
};

vector<node> s;
int B[N], le, ans[N];

// 离散化映射
int id(int G) {
    return lower_bound(B + 1, B + 1 + le, G) - B;
}

// 树状数组
int c[N];
void upd(int pos, int k) {
    for (int i = pos; i <= le; i += (i & (-i)))
        c[i] += k;
}

int qy(int pos) {
    int res = 0;
    for (int i = pos; i; i -= (i & (-i)))
        res += c[i];
    return res;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> Q;
    
    // 处理染色操作
    for (int i = 1; i <= n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        auto [lx, rx] = cov(x);
        auto [ly, ry] = cov(y);
        
        // 二维差分
        s.push_back({lx, ly, 1, c});
        s.push_back({lx, ry, 1, -c});
        s.push_back({rx, ly, 1, -c});
        s.push_back({rx, ry, 1, c});
        
        B[++le] = rx;
        B[++le] = ry;
    }
    
    // 处理查询操作
    for (int i = 1; i <= Q; i++) {
        int x, y;
        cin >> x >> y;
        s.push_back({rev(x), rev(y), 2, i});  // 查询点转换
        B[++le] = rev(y);
    }
    
    // 按x坐标排序
    sort(s.begin(), s.end(), [&](node p, node q) {
        if (p.x != q.x) return p.x < q.x;
        if (p.y != q.y) return p.y < q.y;
        return p.op < q.op;
    });
    
    // 离散化y坐标
    sort(B + 1, B + 1 + le);
    le = unique(B + 1, B + 1 + le) - B - 1;
    
    // 扫描线处理
    for (auto [x, y, op, v] : s) {
        if (op == 1) {
            upd(id(y), v);  // 更新树状数组
        } else {
            ans[v] = qy(id(y));  // 查询
        }
    }
    
    // 输出答案
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << '\n';
    
    return 0;
}

关键优化

1. 坐标变换技巧

• 将无限周期性网格映射为有限矩形
• 利用二进制逆序保持空间局部性

2. 二维差分

• 将矩形区域操作转为四个点的操作
• 支持区间修改、单点查询

3. 扫描线 + 树状数组

• 将二维问题降为一维
• $O(\log n)$ 完成每次操作

4. 离散化

• 处理 $10^{18}$ 级别的坐标
• 减少空间开销

复杂度分析

• 时间复杂度：$O((N + Q) \log (N + Q))$
  • 排序：$O((N + Q) \log (N + Q))$
  • 树状数组操作：$O((N + Q) \log (N + Q))$
• 空间复杂度：$O(N + Q)$

对于 $N, Q \leq 2 \times 10^5$ 的数据规模，该算法能够高效运行。

算法正确性

1. 坐标变换正确性：保证原问题的周期性在新坐标系中变为矩形区域
2. 差分正确性：二维差分准确记录区域染色值
3. 查询正确性：扫描线过程中树状数组维护当前 $x$ 位置的所有 $y$ 坐标值

该算法通过巧妙的坐标变换和数据结构组合，高效解决了大规模周期性染色查询问题。