[CCC 2019] Triangle: The Data Structure

题意

给定边长为 $n$ 的数字三角形（第 $i$ 行有 $i$ 个数）。对每个边长为 $k$ 的正子三角形求其中数字的最大值，再把所有子三角形的最大值求和。

思路

先看一个直接按题意扫描的朴素解：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, k;
int a[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    long long answer = 0;

    // 枚举每个大小为 k 的正三角形的顶点。
    for (int i = 1; i + k - 1 <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int best = 0;

            // 直接把这个子三角形里的所有点扫一遍，取最大值。
            for (int dx = 0; dx < k; dx++) {
                for (int dy = 0; dy <= dx; dy++) {
                    best = max(best, a[i + dx][j + dy]);
                }
            }

            answer += best;
        }
    }

    cout << answer << '\n';
    return 0;
}

暴力对每个子三角形逐行扫一遍取最大值，总复杂度 $O(n^2 k^2)$ ， $n \le 3000$ 时不可行。

为什么要倍增？

"对所有子三角形分别求最大值"和 RMQ 非常像——RMQ 用 ST 表把区间最值拆成两个 $2^j$ 长度的重叠区间。这里也是：预处理出边长为 $2^j$ 的三角形的最大值，查询时用少量完全覆盖的预计算块拼出目标三角形。

怎么拼？

一维 ST 表只需要两块。但在二维等边三角形上，只用三个"角"上的小三角形覆盖大三角形会漏掉中央区域。

解法是用正三角形和倒三角形两种形状配合：一个边长为 $s$ 的大三角形可以分解成 $s = p + d$ ，其中 $p$ 是不超过 $s$ 的最大 $2$ 的幂， $d = s - p$ 。大三角形被 $3$ 个边长为 $p$ 的三角形覆盖，必要时再用 $1$ 个倒三角形补上间隙——总共 $3 \sim 4$ 个预计算块。

对每种边长 $s$ ，先递归求出 $p$ 和可能需要的倒三角形的倍增表，再按递推公式合并，得到 $s$ 边的所有位置的最大值。

实现要点

坐标：三角形位置用 $(x, y)$ 坐标表示（ $x \ge 0, y \ge 0, x + y \le n - 1$ ），与读入的行/列一一对应。
DAG 计算：所有需要的"边长 $\times$ 形状"组合构成一个节点图，边长为 $1$ 的叶子直接存原始数据，大边长按拓扑序（边长从小到大）递推，计算完就释放不再需要的子节点内存。
滚动：每个节点只在计算时分配内存，用毕即释，总空间 $O(n^2)$ 。
求和：最终根节点（边长 $k$ 的正三角形）的 data 数组保存了所有位置的最大值，直接累加即可。

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304#include <bits/stdc++.h>
using namespace std;

const int MAXK = 3005;
const int BUF_SIZE = 1 << 20;

struct FastIO {
    char buf[BUF_SIZE];
    int pos, len;

    FastIO() {
        pos = 0;
        len = 0;
    }

    inline int gc() {
        if (pos == len) {
            len = fread(buf, 1, BUF_SIZE, stdin);
            pos = 0;
            if (len == 0) {
                return EOF;
            }
        }
        return buf[pos++];
    }

    template <typename T>
    inline void read(T &x) {
        x = 0;
        int sign = 1;
        int c = gc();
        while (c != '-' && (c < '0' || c > '9')) {
            c = gc();
        }
        if (c == '-') {
            sign = -1;
            c = gc();
        }
        while (c >= '0' && c <= '9') {
            x = x * 10 + c - '0';
            c = gc();
        }
        x *= sign;
    }
} io;

struct Node {
    int type;           // 0: 正三角形, 1: 倒三角形
    int s;              // 当前三角形的边长
    int m;              // 可用坐标满足 x + y <= m
    int p, d, t;        // 递推参数
    int dep1;           // 同方向的较小三角形
    int dep2;           // 中间补的反向三角形，不存在时为 -1
    int use_count;      // 还有多少父状态会用到我
    int *data;          // 这一层所有位置的最大值
};

int n, k;
int down_id[MAXK];
int up_id[MAXK];
vector<Node> nodes;

inline int triangle_size(int m) {
    return (m + 1) * (m + 2) / 2;
}

inline int row_start(int m, int x) {
    return x * (m + 1) - x * (x - 1) / 2;
}

inline int highest_power_less_than(int x) {
    int p = 1;
    while ((p << 1) < x) {
        p <<= 1;
    }
    return p;
}

int build_node(int type, int s) {
    int &slot = (type == 0 ? down_id[s] : up_id[s]);
    if (slot != -1) {
        return slot;
    }

    Node node;
    node.type = type;
    node.s = s;
    node.m = (type == 0 ? n - s : n - 2 * s + 1);
    node.p = node.d = node.t = 0;
    node.dep1 = node.dep2 = -1;
    node.use_count = 0;
    node.data = nullptr;

    int id = (int)nodes.size();
    nodes.push_back(node);
    slot = id;

    if (s == 1) {
        return id;
    }

    nodes[id].p = highest_power_less_than(s);
    nodes[id].d = s - nodes[id].p;
    nodes[id].t = 2 * nodes[id].d - nodes[id].p - 1;

    nodes[id].dep1 = build_node(type, nodes[id].p);
    nodes[nodes[id].dep1].use_count++;

    if (nodes[id].t > 0) {
        nodes[id].dep2 = build_node(type ^ 1, nodes[id].t);
        nodes[nodes[id].dep2].use_count++;
    }

    return id;
}

void build_base_layer(const vector<int> &base) {
    int base_id_down = down_id[1];
    if (base_id_down != -1) {
        int sz = triangle_size(n - 1);
        nodes[base_id_down].data = new int[sz];
        memcpy(nodes[base_id_down].data, &base[0], sizeof(int) * sz);
    }

    int base_id_up = up_id[1];
    if (base_id_up != -1) {
        int sz = triangle_size(n - 1);
        nodes[base_id_up].data = new int[sz];
        memcpy(nodes[base_id_up].data, &base[0], sizeof(int) * sz);
    }
}

void free_node_if_unused(int id, int root_id) {
    if (id == -1 || id == root_id) {
        return;
    }
    if (nodes[id].use_count == 0 && nodes[id].data != nullptr) {
        delete[] nodes[id].data;
        nodes[id].data = nullptr;
    }
}

void compute_down(int id) {
    Node &cur = nodes[id];
    Node &same = nodes[cur.dep1];
    int *a = same.data;

    int total = triangle_size(cur.m);
    cur.data = new int[total];

    if (cur.dep2 == -1) {
        for (int x = 0; x <= cur.m; x++) {
            int len = cur.m - x + 1;
            int cur_row = row_start(cur.m, x);
            int row1 = row_start(same.m, x);
            int row2 = row_start(same.m, x + cur.d);
            for (int y = 0; y < len; y++) {
                int v1 = a[row1 + y];
                int v2 = a[row2 + y];
                int v3 = a[row1 + y + cur.d];
                cur.data[cur_row + y] = max(v1, max(v2, v3));
            }
        }
        return;
    }

    Node &other = nodes[cur.dep2];
    int *b = other.data;

    for (int x = 0; x <= cur.m; x++) {
        int len = cur.m - x + 1;
        int cur_row = row_start(cur.m, x);
        int row1 = row_start(same.m, x);
        int row2 = row_start(same.m, x + cur.d);
        int row4 = row_start(other.m, x + cur.d - cur.t);
        for (int y = 0; y < len; y++) {
            int v1 = a[row1 + y];
            int v2 = a[row2 + y];
            int v3 = a[row1 + y + cur.d];
            int v4 = b[row4 + y + cur.d - cur.t];
            cur.data[cur_row + y] = max(max(v1, v2), max(v3, v4));
        }
    }
}

void compute_up(int id) {
    Node &cur = nodes[id];
    Node &same = nodes[cur.dep1];
    int *a = same.data;

    int total = triangle_size(cur.m);
    cur.data = new int[total];

    if (cur.dep2 == -1) {
        for (int x = 0; x <= cur.m; x++) {
            int len = cur.m - x + 1;
            int cur_row = row_start(cur.m, x);
            int row1 = row_start(same.m, x + cur.d);
            int row3 = row_start(same.m, x);
            for (int y = 0; y < len; y++) {
                int v1 = a[row1 + y + cur.d];
                int v2 = a[row1 + y];
                int v3 = a[row3 + y + cur.d];
                cur.data[cur_row + y] = max(v1, max(v2, v3));
            }
        }
        return;
    }

    Node &other = nodes[cur.dep2];
    int *b = other.data;

    for (int x = 0; x <= cur.m; x++) {
        int len = cur.m - x + 1;
        int cur_row = row_start(cur.m, x);
        int row1 = row_start(same.m, x + cur.d);
        int row3 = row_start(same.m, x);
        int row4 = row_start(other.m, x + cur.p);
        for (int y = 0; y < len; y++) {
            int v1 = a[row1 + y + cur.d];
            int v2 = a[row1 + y];
            int v3 = a[row3 + y + cur.d];
            int v4 = b[row4 + y + cur.p];
            cur.data[cur_row + y] = max(max(v1, v2), max(v3, v4));
        }
    }
}

int main() {
    memset(down_id, -1, sizeof(down_id));
    memset(up_id, -1, sizeof(up_id));

    io.read(n);
    io.read(k);

    int base_m = n - 1;
    vector<int> base(triangle_size(base_m));

    // 读入时把普通的“按行编号”转成两轴坐标 (x, y)。
    // 原三角形第 i 行第 j 个数，对应坐标：
    // x = j - 1, y = i - j
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int x = j - 1;
            int y = i - j;
            int value;
            io.read(value);
            base[row_start(base_m, x) + y] = value;
        }
    }

    int root_id = build_node(0, k);
    build_base_layer(base);
    vector<int>().swap(base);

    vector<int> order;
    order.reserve(nodes.size());
    for (int i = 0; i < (int)nodes.size(); i++) {
        order.push_back(i);
    }
    sort(order.begin(), order.end(), [](int lhs, int rhs) {
        if (nodes[lhs].s != nodes[rhs].s) {
            return nodes[lhs].s < nodes[rhs].s;
        }
        return nodes[lhs].type < nodes[rhs].type;
    });

    for (int id : order) {
        if (nodes[id].s == 1) {
            continue;
        }

        if (nodes[id].type == 0) {
            compute_down(id);
        }
        else {
            compute_up(id);
        }

        nodes[nodes[id].dep1].use_count--;
        free_node_if_unused(nodes[id].dep1, root_id);

        if (nodes[id].dep2 != -1) {
            nodes[nodes[id].dep2].use_count--;
            free_node_if_unused(nodes[id].dep2, root_id);
        }
    }

    long long answer = 0;
    int total = triangle_size(nodes[root_id].m);
    for (int i = 0; i < total; i++) {
        answer += nodes[root_id].data[i];
    }

    printf("%lld\n", answer);

    for (int i = 0; i < (int)nodes.size(); i++) {
        if (nodes[i].data != nullptr) {
            delete[] nodes[i].data;
            nodes[i].data = nullptr;
        }
    }
    return 0;
}

复杂度

每个"边长"节点处理 $O(n^2)$ 个位置。不同 $p$ 的值（ $2$ 的幂）只有 $O(\log n)$ 种，加上倒三角形，总节点数 $O(\log n)$ 。时间 $O(n^2 \log n)$ ，空间 $O(n^2)$ 。

总结

二维 ST 表不能把一维的"两块覆盖"简单照搬。三角形的特殊形状使得正方向覆盖会出现空隙，引入倒三角形补上间隙，是一种通用的倍增适配思路。DAG 拓扑递推在内存紧张时也能做到"算完即释"，避免保留所有 $O(\log n)$ 层的全量数据。

[CCC 2019] Triangle: The Data Structure

目录

题意

思路

代码

复杂度

总结