马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
人生第一道通讯题！
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;
- }
|
发表于