洛谷-P11403 [RMI 2020] 软盘 / Floppy 题解
注意到，区间最值可以转化成笛卡尔树上 LCA。因此只需要传笛卡尔树即可。
考虑单调栈建树过程。用 0/10/1 表示进出栈，这样就可以重现建树过程，从而唯一确定树的形态。
由于每个点最多进出栈各一次，因此字符串长度 ≤2�≤2N。
Code
#include "floppy.h" |
#include <bits/stdc++.h> |
#define rep(i,a,b) for(int i(a);i<b;++i) |
#define per(i,a,b) for(int i(a);i>b;--i) |
#define rept(i,a,b) for(int i(a);i<=b;++i) |
#define pert(i,a,b) for(int i(a);i>=b;--i) |
#define pb push_back |
#define eb emplace_back |
using namespace std; |
constexpr int N=4e4+5; |
int st[N],l[N],r[N],fa[16][N],dep[N]; |
string s; |
void read_array(int subtask_id,const vector<int> &v){ |
int n=v.size(),top=0; |
s.clear(); |
rep(i,0,n){ |
while(top&&v[st[top]]<v[i]) --top,s.pb('0'); |
st[++top]=i,s.pb('1'); |
} |
save_to_floppy(s); |
} |
void dfs(int u){ |
dep[u]=dep[fa[0][u]]+1; |
rept(i,1,15) fa[i][u]=fa[i-1][fa[i-1][u]]; |
if(l[u]) fa[0][l[u]]=u,dfs(l[u]); |
if(r[u]) fa[0][r[u]]=u,dfs(r[u]); |
} |
int lca(int u,int v){ |
if(dep[u]<dep[v]) u^=v^=u^=v; |
int d=dep[u]-dep[v]; |
rept(i,0,15) if(d>>i&1) u=fa[i][u]; |
if(u==v) return u; |
pert(i,15,0) if(fa[i][u]^fa[i][v]) u=fa[i][u],v=fa[i][v]; |
return fa[0][u]; |
} |
vector<int> solve_queries(int subtask_id,int N,const string &bits,const vector<int> &a, const vector<int> &b){ |
vector<int> ans; |
int top=0,p=0; |
rept(i,1,N){ |
int lst=0; |
while(bits[p]=='0') lst=st[top--],++p; |
if(lst) l[i]=lst; |
if(top) r[st[top]]=i; |
st[++top]=i,++p; |
} |
dfs(st[1]); |
rep(i,0,a.size()) ans.eb(lca(a[i]+1,b[i]+1)-1); // 注意这里节点编号从1开始 |
return ans; |
} |