「Mokia」莫基亚

形式化题目

维护一个初始全 $0$ 的 $W \times W$ 矩阵（下标从 $1$ 开始），依次处理若干操作：

修改：给格子 $(x, y)$ 的权值增加 $a$ ；
询问：求以 $(x_1, y_1)$ 为左下角、 $(x_2, y_2)$ 为右上角的子矩阵内所有权值之和。

修改操作数 $M \leqslant 160000$ ，询问次数 $Q \leqslant 10000$ ， $W \leqslant 2000000$ ， $1 \leqslant a \leqslant 10000$ 。矩阵是稀疏的（被修改的格子数不超过 $M$ ），但坐标值域极大。

正解

思路

朴素做法。 直接开一个 $W \times W$ 的数组模拟：修改 $O(1)$ ，询问要把子矩阵逐格累加，最坏 $O(W^2)$ 。 $W$ 高达 $2 \times 10^6$ ，光存数组就需要 $4 \times 10^{12}$ 个格子，时间和空间都不可行。

第一步优化：单点插入 + 前缀和。 子矩阵和可以用四个二维前缀和角点做容斥：

\mathrm{sum}(x_1,y_1,x_2,y_2) = F(x_2,y_2) - F(x_1-1,y_2) - F(x_2,y_1-1) + F(x_1-1,y_1-1)

其中 $F(X,Y)$ 表示矩形 $[1,X] \times [1,Y]$ 内所有权值之和。于是问题变成：在任意时刻询问二维前缀和 $F(X,Y)$ 。

第二步优化：把"时刻"变成一维偏序。 由于修改在时间上单调累加， $F(X,Y)$ 只依赖于"当前已经发生的修改"。把每个修改记成一个点 $(t, x, y, a)$ （ $t$ 为操作序号），把每个询问角点 $(X, Y)$ 记成 $(t, X, Y)$ ，那么这个角点的答案就是所有满足

t' < t,\quad x' \leqslant X,\quad y' \leqslant Y

的修改点权值 $a'$ 之和——这是一个标准的三维偏序求和问题（时间严格在前，两个坐标分量不超过询问角点）。

第三步：CDQ 分治 + 树状数组。 类似三维偏序求个数，采用"时间维分治，一维排序，一维数据结构"的套路：

把修改点和询问角点统一成事件序列，按下标（即时间）分治 $[l, r]$ ；
递归处理完左右两半的内部贡献后，计算左半的修改点对右半的询问角点的贡献：此时左半的时间天然全部早于右半，只剩二维偏序；
两半各自按 $x$ 归并有序（分治时顺手归并，代替预排序），用双指针把 $x' \leqslant X$ 的修改点插入树状数组（按下标 $y$ 加 $a$ ），每个询问角点用 $Y$ 查询前缀和即可。

注意坐标可能是 $0$ （容斥会出现 $x_1 - 1 = 0$ 、 $y_1 - 1 = 0$ ），树状数组查询下标 $0$ 时返回 $0$ ，插入下标不会为 $0$ （修改坐标 $\geqslant 1$ ），无需平移。

下图展示一次询问被拆成 4 个角点、以及左半修改如何通过树状数组贡献给右半询问的过程：

flowchart LR
    subgraph L["分治左半（时间早）"]
        M1["修改 (t,x,y,+a)"]
        M2["修改 ..."]
    end
    subgraph R["分治右半（时间晚）"]
        P1["角点 (t,X,Y) 按 x 归并扫描"]
    end
    M1 -->|"x' <= X 时插入 BIT(y)"| BIT["树状数组（按 y 前缀和）"]
    M2 -->|"x' <= X 时插入 BIT(y)"| BIT
    BIT -->|"query(Y) 得 Σa'"| P1

每个角点拿到的是"时间在本层分治左侧"的修改贡献；所有包含它的 $O(\log M)$ 层累加起来，恰好等于全部更早修改的贡献，最终按容斥符号组合出子矩阵和。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// Mokia：三维偏序（时间, x, y），CDQ 分治时间维，x 排序后树状数组维护 y。
#include <cstdio>
#include <vector>

typedef long long ll;

struct Ev {
    ll x, y;
    ll w;   // 修改的权值
    ll qid; // 询问编号；-1 表示这是修改
    ll sgn; // 询问角点的符号
};

std::vector<Ev> ev;
std::vector<Ev> tmp;
ll W;
std::vector<ll> tree;
std::vector<int> stamp;
ll cur_stamp = 0;
std::vector<ll> ans;
ll qcnt = 0;

void cdq(ll l, ll r) {
    if (r - l <= 1) return;
    ll mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid, r);
    // 递归保证两半各自按 x 有序；左半修改（时间早）贡献给右半询问
    cur_stamp++;
    ll i = l;
    for (ll j = mid; j < r; j++) {
        if (ev[j].qid == -1) continue;
        ll qx = ev[j].x, qy = ev[j].y;
        while (i < mid && ev[i].x <= qx) {
            if (ev[i].qid == -1) {
                ll k = ev[i].y, ew = ev[i].w;
                while (k <= W) {
                    if (stamp[k] != cur_stamp) {
                        stamp[k] = (int)cur_stamp;
                        tree[k] = 0;
                    }
                    tree[k] += ew;
                    k += k & -k;
                }
            }
            i++;
        }
        if (ev[j].sgn) {
            ll s = 0, k = qy;
            while (k) {
                if (stamp[k] == cur_stamp) s += tree[k];
                k -= k & -k;
            }
            ans[ev[j].qid] += ev[j].sgn * s;
        }
    }
    // 归并两半按 x 有序，维持不变式
    ll a = l, b = mid, t = l;
    while (a < mid && b < r) {
        if (ev[a].x <= ev[b].x) tmp[t++] = ev[a++];
        else tmp[t++] = ev[b++];
    }
    while (a < mid) tmp[t++] = ev[a++];
    while (b < r) tmp[t++] = ev[b++];
    for (ll k = l; k < r; k++) ev[k] = tmp[k];
}

int main() {
    ll S;
    if (scanf("%lld %lld", &S, &W) != 2) return 0; // 空输入安全返回

    tree.assign(W + 1, 0);
    stamp.assign(W + 1, 0);

    while (true) {
        ll op;
        if (scanf("%lld", &op) != 1) break;
        if (op == 1) {
            ll x, y, a;
            scanf("%lld %lld %lld", &x, &y, &a);
            Ev e;
            e.x = x; e.y = y; e.w = a; e.qid = -1; e.sgn = 0;
            ev.push_back(e);
        } else if (op == 2) {
            ll x1, y1, x2, y2;
            scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
            // 每个询问拆成 4 个前缀角点询问
            Ev e;
            e.x = x1 - 1; e.y = y1 - 1; e.w = 0; e.qid = qcnt; e.sgn = 1;  ev.push_back(e);
            e.x = x2;     e.y = y2;     e.w = 0; e.qid = qcnt; e.sgn = 1;  ev.push_back(e);
            e.x = x1 - 1; e.y = y2;     e.w = 0; e.qid = qcnt; e.sgn = -1; ev.push_back(e);
            e.x = x2;     e.y = y1 - 1; e.w = 0; e.qid = qcnt; e.sgn = -1; ev.push_back(e);
            qcnt++;
        } else {
            break;
        }
    }

    ans.assign(qcnt, 0);
    tmp.resize(ev.size());
    if (!ev.empty()) cdq(0, (ll)ev.size());

    for (ll i = 0; i < qcnt; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81import sys

def main():
    data = iter(map(int, sys.stdin.buffer.read().split()))
    S = next(data)  # S 保证为 0，无需处理
    W = next(data)

    # 每个询问 (x1,y1,x2,y2) 拆成 4 个前缀角点询问 f(X,Y)=时间更早的修改中
    # 满足 x<=X 且 y<=Y 的权值和：f(x2,y2)-f(x1-1,y2)-f(x2,y1-1)+f(x1-1,y1-1)。
    # 这样问题变成三维偏序（时间, x, y）：CDQ 分治时间维，x 排序后树状数组维护 y。
    ev = []  # (x, y, w, qid, sgn)；修改 qid=-1，询问角点带 qid 与符号 sgn
    cnt = 0
    while True:
        op = next(data)
        if op == 1:
            x, y, a = next(data), next(data), next(data)
            ev.append((x, y, a, -1, 0))
        elif op == 2:
            x1, y1, x2, y2 = next(data), next(data), next(data), next(data)
            ev.append((x1 - 1, y1 - 1, 0, cnt, 1))
            ev.append((x2, y2, 0, cnt, 1))
            ev.append((x1 - 1, y2, 0, cnt, -1))
            ev.append((x2, y1 - 1, 0, cnt, -1))
            cnt += 1
        else:
            break

    m = len(ev)
    ans = [0] * cnt
    tree = [0] * (W + 1)  # 树状数组按下标 y 维护
    stamp = [0] * (W + 1)  # 时间戳清零，免去每层回滚
    cur = 0

    def solve(l, r):
        nonlocal cur
        if r - l <= 1:
            return
        mid = (l + r) >> 1
        solve(l, mid)
        solve(mid, r)
        # 递归保证两半各自按 x 有序；左半修改（时间早）贡献给右半询问
        cur += 1
        i = l
        for j in range(mid, r):
            qx, qy, _, qid, sgn = ev[j]
            if qid == -1:
                continue
            while i < mid and ev[i][0] <= qx:
                ex, ey, ew, eq, _ = ev[i]
                if eq == -1:
                    k = ey
                    while k <= W:
                        if stamp[k] != cur:
                            stamp[k] = cur
                            tree[k] = 0
                        tree[k] += ew
                        k += k & -k
                i += 1
            if sgn:
                s = 0
                k = qy
                while k:
                    if stamp[k] == cur:
                        s += tree[k]
                    k -= k & -k
                ans[qid] += sgn * s
        # 归并两半按 x 有序，维持不变式
        tmp = []
        a, b = l, mid
        while a < mid and b < r:
            if ev[a][0] <= ev[b][0]:
                tmp.append(ev[a]); a += 1
            else:
                tmp.append(ev[b]); b += 1
        tmp.extend(ev[a:mid]); tmp.extend(ev[b:r])
        ev[l:r] = tmp

    solve(0, m)
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

main()

复杂度

设事件总数 $N = M + 4Q \leqslant 2 \times 10^5$ 。CDQ 分治共 $O(\log N)$ 层，每层双指针加树状数组操作共 $O(N \log W)$ ，总时间复杂度 $O(N \log N \log W)$ ；树状数组大小 $O(W)$ ，事件数组 $O(N)$ ，空间约 $O(W + N)$ 。实测最大数据约 $2$ 秒（Python 常数较大，算法复杂度与标准 C++ 解法同阶）。

总结

稀疏矩阵的单点加 + 子矩阵求和，不要被 $W \leqslant 2 \times 10^6$ 吓到：真正参与运算的只有 $M$ 个修改点。
核心转化链：子矩阵和 $\to$ 四角容斥的二维前缀和 $\to$ 引入时间维后的三维偏序求和 $\to$ CDQ 分治（时间）+ 归并（ $x$ ）+ 树状数组（ $y$ ）。
实现细节：询问拆角点时坐标会出现 $0$ ；分治内用"时间戳清零"的树状数组，避免每层 $O(W)$ 回滚；左右两半按 $x$ 归并保持有序，省去每层重新排序。

图示解析

样例推演

以样例为例（ $W=4$ ）：先修改 $(2,3) \mathrel{+}= 3$ ，再询问 $[1,1]\times[3,3]$ 。询问拆成 4 个角点，下表列出每个角点命中的修改点与容斥符号：

角点 $(X, Y)$	容斥符号	命中的修改（ $x' \leqslant X, y' \leqslant Y$ ）	贡献
$(3, 3)$	$+$	$(2, 3)$	$+3$
$(0, 3)$	$-$	无（ $X=0$ ）	$0$
$(3, 2)$	$-$	无（ $y'=3 > 2$ ）	$0$
$(0, 2)$	$+$	无	$0$

四个角点的贡献相加得 $3$ ，与样例输出一致。第二个询问 $[2,2]\times[3,4]$ 同理：角点 $(3,4)$ 与 $(3,2)$ 命中两次修改点 $(2,2)$ 与 $(2,3)$ ，容斥后得 $2+3=5$ 。

观察重点是：每个角点本身只做一次"历史修改中 $x, y$ 双不超过"的前缀统计，容斥只是把 4 次这样的统计组合起来；而"历史"这一维由 CDQ 分治保证——任何一对（早修改，晚询问）恰好在分治树的某一层被计入一次。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

样例推演