AT_abc417_g 题解
ChatSheep
·
·
题解
一种学数据结构学傻了的做法。
题意
定义长度为 Q+1 的字符串序列 S：
-
-
- 对于 2 \le i \le Q+1，S_i = S_{L_i} + S_{R_i}（其中 L_i, R_i 是输入给定的下标）。
### 题解
考虑如下 $O(Q^2)$ 做法：
- 若要查询第 $i$ 个字符串（$S_i$）中第 $x$ 个字符（$(S_i)_x$），执行以下操作：
- 如果 $i=0,1$，$O(1)$ 得到答案。
- 如果 $x\le|S_{L_i}|$，那么 $(S_i)_x$ 这个字符一定是来源于字符串 $S_{L_i}$，因此问题即可转化为求解 $(S_{L_i})_x$。
- 如果 $x>|S_{L_i}|$，那么 $(S_i)_x$ 这个字符一定是来源于字符串 $S_{R_i}$，因此问题即可转化为求解 $(S_{R_i})_{x-|L_i|}$。
$|S_i|$ 是可以简单处理的，因为 $x\le 10^{18}$，所以无需高精度，把 $|S_i|$ 对 $10^{18}$ 取 $\min$ 即可。
考虑离线处理，在读入完后，就把询问挂在对应的节点上，然后枚举 $Q\to 1$，把当前节点挂的询问做一个批量转移，转移就两种，要么转移到 $L_i$，要么转移到 $R_i$ 并且询问的位置整体减去 $|S_{L_i}|$。
而这个数据结构要做的就是把第 $i$ 个集合按照给定的值分裂成两个集合 $l,r$，把 $l$ 集合合并到一个集合（$L_i$ 对应的集合），把 $r$ 集合每一个元素减 $|S_{L_i}|$ 合并到另一个集合（$R_i$ 对应的集合）。
合并完后，编号为 $0$ 的集合中所有的元素对应的答案字符就是 $\texttt 0$，编号为 $1$ 的集合中所有的元素对应的答案字符就是 $\texttt 1$。
可以使用平衡树解决此问题，然而因为询问的 $X_i$ 是任意的，会很难处理合并的两个平衡树值域有交的情况，所以使用启发式合并或者归并即可。
具体实现可以参考[这篇题解](https://www.luogu.com.cn/article/p4ejw9j6)，因为是平衡树模板之一，故不赘述，时间复杂度两只 $\log$。
### 代码
此处展示核心代码：
```cpp
int n, l[500005], r[500005], x[500005], sz[500005], rt[500005];
void solve() {
cin >> n;
sz[1] = 1;
sz[2] = 1;
for (int i = 3; i <= n + 2; ++i) {
cin >> l[i] >> r[i] >> x[i];
l[i] += 1; // 下标整体加一防止程序异常对 0 号节点处理
r[i] += 1;
sz[i] = sz[l[i]] + sz[r[i]];
sz[i] = min(sz[i], 1ll << 61); // 设置 sz 上限
rt[i] = t.make(x[i]); // 创建一个值为 x[i] 的节点，在平衡树中的标号为 i-2，这样即可方便输出答案。
}
for (int i = n + 2; i >= 3; --i) {
int L, R;
int mid = sz[l[i]];
t.split(rt[i], mid, L, R); // L 是 <= mid 的，R 是 > mid 的
t.add(R, -mid); // 整体加一个值，需要用懒标记
rt[l[i]] = t.Merge(rt[l[i]], L); // 合并两个值域可能有交集的平衡树
rt[r[i]] = t.Merge(rt[r[i]], R);
}
t.fill(rt[1], 0); // 把整个树所有的节点对应的 ans 设置为 0
t.fill(rt[2], 1);
for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
}
```
[此处为完整代码](https://atcoder.jp/contests/abc417/submissions/68152943)。需要一定卡常。