洛谷-P11403 [RMI 2020] 软盘 / Floppy 题解-尧图网站建设

📅 发布时间：2026/7/2 5:16:35

注意到，区间最值可以转化成笛卡尔树上 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;

}