题解：P16762 [GKS 2020 #D] Locked Doors
GX6zm
·
·
题解
题意
有 N 个房间排成一行，相邻房间之间有难度互不相同的门。
从房间 S 开始拍照，之后每次在当前已访问区间左右两侧的门中，选择难度较小的门打开，并进入新房间拍照。
从房间 $S$ 开始，第 $K$ 个拍照的房间是哪个？
## 题解
无论从哪个房间开始，最后一定会访问完所有房间，我们试着从这个最终状态反推。
设当前区间内难度最大的门为 $D_m$，以它为界把区间分为两部分。观察能够得到：Bangles 在打开 $D_m$ 前，一定访问完了起点 $S$ 所在部分，而另一侧会在最后被**顺序**访问。
可以直接排除不包含起点的部分，然后对包含起点的剩余区间继续寻找最大门进行分治。重复上述过程，即可找到第 $K$ 个被访问的房间。
这个结构每次都在寻找当前区间的最大值然后递归左右部分，这不是很符合大根笛卡尔树的结构吗？
具体地，对数组 $A$ 建立大根笛卡尔树，数组下标满足 BST 性质，数组元素满足大根堆性质。
为了从房间出发进行查询，我们需要在笛卡尔树中补上叶子节点来表示房间。
对于节点 $u$：
- 若其没有左孩子，则房间 $u$ 作为其左叶子。
- 若其没有右孩子，则房间 $u+1$ 作为其右叶子。
这样能够不重不漏地把所有房间添加到树中。
原本的反推相当于在笛卡尔树上面由上到下，建好了树之后即可改为由下到上顺推，这样就能倍增加速。
对每个节点 $u$，预处理以下信息：
- $\text{cnt}_u$：子树中的房间数。
- $L_u, R_u$：子树覆盖的房间区间边界。
- $\text{fa}_{u, j}$：节点 $u$ 的第 $2^j$ 个祖先。
我们需要从房间 $S$ 对应的叶子节点向上找到一个节点 $u$，使得从 $S$ 到 $u$ 的路径上，包含 $S$ 的那个孩子节点 $v$ 满足 $\text{cnt}_v < K$，但 $\text{cnt}_u \ge K$。
找到节点 $u$ 后：
- 若 $S \le u$（起点在左侧），说明右侧房间是按从左到右顺序访问的，答案为 $L_u + K - 1$。
- 若 $S > u$（起点在右侧），说明左侧房间是按从右到左顺序访问的，答案为 $R_u - K + 1$。
时间复杂度：$\mathcal{O}(N \log N + Q \log N)$。
空间复杂度：$\mathcal{O}(N \log N)$。
::::info[代码]
```cpp
#include<bits/stdc++.h>
#define lc t[u].ls
#define rc t[u].rs
using namespace std;
constexpr int N = 1e5 + 7, M = 2e5 + 7, LOG = 20;
int T, n, q;
int a[M], st[N], top;
int fa[LOG][M];
struct node{
int ls, rs, fa;
int val, L, R;
void init(){
ls = rs = fa = 0;
val = L = R = 0;
}
}t[M];
void init(){
top = 0;
for (int i = 1; i <= 2 * n; i++)
t[i].init();
}
void dfs(int u){
if (u == 0) return;
fa[0][u] = t[u].fa;
for (int i = 1; i < LOG; i++)
fa[i][u] = fa[i - 1][fa[i - 1][u]];
if (u >= n){
t[u].val = 1;
return;
}
dfs(t[u].ls), t[u].val += t[lc].val, t[u].L = t[lc].L;
dfs(t[u].rs), t[u].val += t[rc].val, t[u].R = t[rc].R;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> T;
for (int _ = 1; _ <= T; _++){
cout << "Case #" << _ << ": ";
cin >> n >> q;
for (int i = 1; i < n; i++)
cin >> a[i];
init();
for (int i = 1; i < n; i++){// 建树
int lst = 0;
while (top && a[st[top]] < a[i])
lst = st[top--];
if (top){
t[st[top]].rs = i;
t[i].fa = st[top];
}
if (lst) t[lst].fa = i;
t[i].ls = lst;
st[++top] = i;
}
for (int i = 1; i < n; i++){// 补房间
if (!t[i].ls){
t[i].ls = i + n - 1;
t[i + n - 1].L = t[i + n - 1].R = i;
t[i + n - 1].fa = i;
}
if (!t[i].rs){
t[i].rs = i + n;
t[i + n ].L = t[i + n].R = i + 1;
t[i + n].fa = i;
}
}
dfs(st[1]);
for (int o = 1; o <= q; o++){
int s, k;
cin >> s >> k;
int u = n - 1 + s;
for (int i = LOG - 1; i >= 0; i--){
int f = fa[i][u];
if (f && t[f].val < k)
u = f;
}
u = fa[0][u];
if (s <= u)
cout << t[u].L + k - 1 << ' ';
else
cout << t[u].R - k + 1 << ' ';
}
cout << '\n';
}
}
```
::::