引入
现在市面上大多数解决 问题的一般是
- 预处理, 回答的线段树,平衡树。
- 预处理, 回答的 表,猫树。
- 预处理, 回答的分块加 表,这种神仙算法。
这里考虑使用 的 预处理, 回答的算法,这里用求区间最大举例。
Cartesian-tree
对于笛卡尔树,我们可以根据性质,对于一个节点 ,它的子树的任意权值都比 要小,因为笛卡尔树是满足 的性质的,所以节点 一定是管辖的一个连续的区间的。根据笛卡尔树的性质,那么 的最大值就是节点 的 的权值。
tarjan
关于 求 。这里是一种离线算法,总的复杂度为 不考虑并查集的常数。这个的讲解网上很全,我这里抛一个链接。如何用 tarjan 求 LCA 。因此我们就得到了 预处理, 回答询问的方法 。其实如果不会 也可以用其它的方法做到 (例如倍增求 )或者其它复杂度的算法。
代码
#include<bits/stdc++.h> using namespace std; struct Query{int id,pos;}; const int N = 2e6 + 1000, M = 1e5 + 1000; inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } vector<Query> q[M]; vector<int> G[M]; int fa[M],vis[M],n,m,root,ans[N],top,val[M],rc[M],lc[M],st[M]; int find(int x) {return fa[x] == x?x:fa[x]=find(fa[x]);} void dfs(int x,int Fa) { for(auto y:G[x]) { if(y == Fa) continue;dfs(y,x);fa[y] = x; } vis[x] = 1; for(auto Q:q[x]) { if(vis[Q.pos]) ans[Q.id] = find(Q.pos); } } int main() { n = read();m = read(); for(int i = 1;i <= n;i++) val[i] = read(); for(int i = 1;i <= n;i++) { int k = top; while(k && val[i] >= val[st[k]]) k--; if(k) rc[st[k]] = i; if(k < top) lc[i] = st[k + 1]; st[++k] = i;top = k; } root = st[1]; for(int i = 1;i <= n;i++) { int a = lc[i],b = rc[i]; if(a) G[i].push_back(a); if(b) G[i].push_back(b); } for(int i = 1;i <= m;i++) { int a = read(),b = read(); q[a].push_back((Query){i,b}); q[b].push_back((Query){i,a}); } for(int i = 1;i <= n;i++) fa[i] = i; dfs(root,0); for(int i = 1;i <= m;i++) printf("%d\n", val[ans[i]]); return 0; }