2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——E. Visualize This · znzryb
## 题目大意
**题目归纳**
给定一个数组大小 $n$ ($1 \le n \le 10^4$)，需要构建并按特定格式可视化一个线段树。
**线段树构建规则**
- **根节点**：对应半开区间 $[0, n)$。
- **分裂规则**：对于非叶子节点 $[L, R)$，其中点为 $M = \lfloor (L+R)/2 \rfloor$。左子节点为 $[L, M)$，右子节点为 $[M, R)$。
- **叶子节点**：对应区间长度为 1 的节点 $[i, i+1)$。
**可视化输出规则**
- **分层输出**：树的根在第一行，子节点在下一行，以此类推。
- **节点格式**：显示为 `[L;R)`。
- **分隔竖线**：如果节点 $[L, R)$ 不是叶子，必须在其分号 `;` 的正下方（即同一列），从该节点的下一行开始直到整个图形的最后一行，绘制竖线 `|`。这表示左右子树的物理分隔。
- **排版约束**：
- 同一行内的元素（节点文本或竖线）之间至少保留 **1 个空格**。
- 在满足对齐条件的前提下，空格数量应**尽可能少**。
- 整个图形靠左对齐（即至少有一行的行首没有空格）。
- 行末不得有多余空格。
**样例展示与解释**
**样例 1** ($n=3$)
```
[0;3)
[0;1) | [1;3)
| [1;2) | [2;3)
```
**解释**：
- **第 1 行**：根节点 $[0, 3)$。其中点为 1，分号 `;` 所在列决定了后续行的主分隔线位置。
- **第 2 行**：
- 左子节点 $[0, 1)$。
- 中间是根节点 $[0, 3)$ 延伸下来的竖线 `|`。
- 右子节点 $[1, 3)$。
- **第 3 行**：
- 左侧空位（因为 $[0, 1)$ 是叶子）。
- 根节点的竖线 `|` 继续延伸。
- $[1, 3)$ 分裂为 $[1, 2)$ 和 $[2, 3)$，中间由 $[1, 3)$ 的分号 `;` 延伸出的竖线 `|` 分隔。
- **对齐**：所有竖线 `|` 都严格位于其父节点 `;` 的正下方，且元素间距最小化。
**样例 2** ($n=7$)
```
[0;7)
[0;3) | [3;7)
[0;1) | [1;3) | [3;5) | [5;7)
| [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7)
```
**解释**：
- 展示了更深层的结构。每一层新产生的分支节点都会在其 `;` 下方产生一条新的竖线，一直延伸到底部。
- 例如，根节点 $[0, 7)$ 的竖线贯穿了第 2、3、4 行。
- 第 2 行的节点 $[0, 3)$ 和 $[3, 7)$ 的竖线分别贯穿了第 3、4 行。
## 思路讲解
这道题目主要就是考验你的一个实现的这个能力。比较建议的实现方法呢，就是这个宽度的计算呢，先使用一个函数进行总的宽度的计算。然后需要注意啊，这道题目不允许出现后导空格，就是它不会自动忽略后导空格。所以你需要在输出的时候把所有的后导空格给 pop back 给 pop 掉。
[https://codeforces.com/gym/106169/submission/363482617](https://codeforces.com/gym/106169/submission/363482617) 因为后导空格 WA 的一发。
然后还有一个点呢，就是这道题目它使用的是左臂右开，0 base 的，那么你最好也仿照它使用左臂右开0 base 的，不要把它，不要用1 base 的做这道题目，1 base 的做这道题目。是会有问题的，因为因为这个嗯，因为一加一个数，然后再 向下整除二，和0加一个数再向下整除二，它其实这个区间是会有不同的。
```cpp
void visualize() {
widths.resize(4 * N + 2);
cal_visual_w(1, 1);
grid.resize(mx_layer + 2, string(widths[1], ' '));
visualize(1, 0, 1);
for (int i = 1; i <= mx_layer; ++i) {
while (!grid[i].empty() && grid[i].back()==' ') {
grid[i].pop_back();
}
cout << grid[i] << "\n";
}
}
void cal_visual_w(ll u, ll layer) {
mx_layer = max(mx_layer, layer);
if (infos[u].l == infos[u].r-1) {
widths[u] = infos[u].to_string().size();
return;
}
cal_visual_w(u << 1, layer + 1);
widths[u] = widths[u << 1] + 3;
cal_visual_w(u << 1 | 1, layer + 1);
widths[u] += widths[u << 1 | 1];
}
// 可视化线段树
void visualize(ll u, ll sc, ll layer) {
if (infos[u].l == infos[u].r-1) {
string label = infos[u].to_string();
for (ll i = 0; i < label.size(); ++i) {
grid[layer][sc + i] = label[i];
}
return;
}
visualize(u << 1, sc, layer + 1);
string label = infos[u].to_string();
ll pos = label.find(';');
ll labStart = sc + widths[u << 1] + 1 - pos;
for (int i=1;i<=mx_layer;++i) {
if (layer+i>mx_layer) break;
grid[layer + i][sc + widths[u << 1] + 1] = '|';
}
// grid[layer + 1][sc + widths[u << 1] + 1] = '|';
// if (layer+2 <= mx_layer) {
// grid[layer+2][sc + widths[u << 1] + 1]='|';
// }
for (ll i = 0; i < label.size(); ++i) {
grid[layer][labStart + i] = label[i];
}
visualize(u << 1 | 1, sc + widths[u << 1] + 3, layer + 1);
}
```
## AC代码
AC
[https://codeforces.com/gym/106169/submission/363483057](https://codeforces.com/gym/106169/submission/363483057)
::: 源代码
```cpp
/**
* Problem: E. Visualize This
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/gym/106169/problem/E
* Created: 2026-02-17 23:05:50
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct Info {
ll l, r, sum;
friend ostream &operator <<(ostream &os, const Info &a) {
os << "[" << a.l << ";" << a.r << ")";
return os;
}
string to_string() const {
stringstream ss;
ss << *this;
return ss.str();
}
};
Info merge(const Info &a, const Info &b) {
return {a.l, b.r, a.sum + b.sum};
}
struct SEG {
ll N;
vector<Info> infos;
SEG(ll N, const vector<Info> &a) {
infos.resize(4 * N + 5);
this->N = N;
build(a, 1, 0, N);
}
void pull(ll u) {
infos[u] = merge(infos[u << 1], infos[u << 1 | 1]);
}
void build(const vector<Info> &a, ll u, ll l, ll r) {
if (l == r-1) {
infos[u] = a[l];
infos[u].l = l;
infos[u].r = r;
return;
}
ll mid = l + r >> 1;
build(a, u << 1, l, mid);
build(a, u << 1 | 1, mid, r);
pull(u);
}
Info query(ll u, ll l, ll r) {
if (infos[u].l >= l && infos[u].r <= r) {
return infos[u];
}
Info res{};
if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
res = merge(res, query(u << 1, l, r));
}
if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
res = merge(res, query(u << 1 | 1, l, r));
}
return res;
}
void assign(ll u, ll pos, const Info &val) {
if (infos[u].l == infos[u].r && infos[u].l == pos) {
infos[u] = val;
infos[u].l = pos;
infos[u].r = pos;
return;
}
if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
assign(u << 1, pos, val);
}
if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
assign(u << 1 | 1, pos, val);
}
pull(u);
}
vector<ll> widths;
vector<string> grid;
ll mx_layer = 0;
void visualize() {
widths.resize(4 * N + 2);
cal_visual_w(1, 1);
grid.resize(mx_layer + 2, string(widths[1], ' '));
visualize(1, 0, 1);
for (int i = 1; i <= mx_layer; ++i) {
while (!grid[i].empty() && grid[i].back()==' ') {
grid[i].pop_back();
}
cout << grid[i] << "\n";
}
}
void cal_visual_w(ll u, ll layer) {
mx_layer = max(mx_layer, layer);
if (infos[u].l == infos[u].r-1) {
widths[u] = infos[u].to_string().size();
return;
}
cal_visual_w(u << 1, layer + 1);
widths[u] = widths[u << 1] + 3;
cal_visual_w(u << 1 | 1, layer + 1);
widths[u] += widths[u << 1 | 1];
}
// 可视化线段树
void visualize(ll u, ll sc, ll layer) {
if (infos[u].l == infos[u].r-1) {
string label = infos[u].to_string();
for (ll i = 0; i < label.size(); ++i) {
grid[layer][sc + i] = label[i];
}
return;
}
visualize(u << 1, sc, layer + 1);
string label = infos[u].to_string();
ll pos = label.find(';');
ll labStart = sc + widths[u << 1] + 1 - pos;
for (int i=1;i<=mx_layer;++i) {
if (layer+i>mx_layer) break;
grid[layer + i][sc + widths[u << 1] + 1] = '|';
}
// grid[layer + 1][sc + widths[u << 1] + 1] = '|';
// if (layer+2 <= mx_layer) {
// grid[layer+2][sc + widths[u << 1] + 1]='|';
// }
for (ll i = 0; i < label.size(); ++i) {
grid[layer][labStart + i] = label[i];
}
visualize(u << 1 | 1, sc + widths[u << 1] + 3, layer + 1);
}
};
void Solve() {
ll N;
cin >> N;
vector<Info> A(N + 2);
SEG seg(N, A);
seg.visualize();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106169/submission/363483057
*/
```
:::