P11403软盘题解中是什么？

人生第一道通信题！ Solution 由题意得，\(L\) 最大值为 \(2N\)。而题目询问的是最大值的下标，这启示我们保存关于相对大小关系的信息。 注意到，区间最值可以转化成笛卡尔树上 LCA。因此只需要传笛卡尔树即可。 考虑单调栈建树过程。用 \(0/1\) 表示进出栈，这样就可以重现建树过程，从而唯一确定树的形态。 由于每个点最多进出栈各一次，因此字符串长度 \(\le 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; }