洛谷-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);ib;i)#define per(i,a,b) for(int i(a);ib;--i)#define rept(i,a,b) for(int i(a);ib;i)#define pert(i,a,b) for(int i(a);ib;--i)#define pb push_back#define eb emplace_backusing namespace std;constexpr int N4e45;int st[N],l[N],r[N],fa[16][N],dep[N];string s;void read_array(int subtask_id,const vectorint v){int nv.size(),top0;s.clear();rep(i,0,n){while(topv[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 ddep[u]-dep[v];rept(i,0,15) if(di1) ufa[i][u];if(uv) return u;pert(i,15,0) if(fa[i][u]^fa[i][v]) ufa[i][u],vfa[i][v];return fa[0][u];}vectorint solve_queries(int subtask_id,int N,const string bits,const vectorint a, const vectorint b){vectorint ans;int top0,p0;rept(i,1,N){int lst0;while(bits[p]0) lstst[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;}