浅谈笛卡尔树
[介绍(百度百科)](笛卡尔树_百度百科 (baidu.com))
笛卡尔树是一种特定的二叉树数据结构,可由数列构造,在范围最值查询、范围\(top_k\)查询(range top k queries)等问题上有广泛应用。它具有堆的有序性,中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成,需要采用基于栈的算法来找到在该数列中的所有最近小数。
特殊的\(treap\)
性质
先说性质感觉会更好理解一些
虽然是"树",但是笛卡尔树其实就是对序列的一个转化
对于树上的任意一点x,左右儿子left,right,以及在原序列上的\(pos\)值,有:
- 树中的元素满足二叉搜索树的性质,要求按照中序遍历得到的序列为原数组序列,各节点的\(pos\)是连续的,\(pos[left]<pos[x]<pos[right]\),(维持原序列的顺序)
- 树中节点满足堆性质,节点的\(val\)值要大于其左右子节点的\(val\)值,\(val[x]<val[left],val[right]\),(大根此时则恰恰相反)
对于笛卡尔树中每个节点都有两个权值\((val,key)\)
建树
可以使用线段树,st表这些数据结构维护区间最大值/最小值,但是没有必要,大多数笛卡尔树的题目都可以通过维护一个单调栈来实现\(O(n)\)的建树
- 使用单调栈维护最右链
- 每次插入当前的\(i\),在单调栈中不停弹出栈顶,直至栈顶\(fa\)满足\(val_{fa} < val_i\),则最后一次弹出的就是\(j\)
- 将\(i\)作为\(fa\)的右儿子,\(j\)作为\(i\)的左儿子
模拟一下就是:
对于序列\(a=\{9,3,7,1,8,12,10,20,15,18,5\}\)
- 添加点\(1\),\(val_1=9\)加入栈
- 添加点\(2\),弹出点\(1\),点\(1\)就是\(fa\)的左儿子,将\(val_2=3\)加入栈,成为栈顶
- 添加点\(3\),\(val_3<val_2\),故成为点\(1\)的右儿子
- .................(见图)
[P5854 【模板】笛卡尔树](P5854 【模板】笛卡尔树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
模板题,求建出树后就可以得到\(ans\)
#include"bits/stdc++.h"
using namespace std;
const int N=1e7+15;
#define inl inline
#define regi register
#define PII pair<int,int>
//#define ll long long
inl int read(void)
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
int rt;int ls[N],rs[N],fa[N],n;
void build(int* a)
{
stack<int> sta;stack<int>().swap(sta);
for(int i=1;i<=n;i++)
{
int j=0;
while(!sta.empty()&&a[sta.top()]>a[i]) j=sta.top(),sta.pop();
if(sta.empty()) rt=i;
else rs[sta.top()]=i;
ls[i]=j;
sta.push(i);
}
}
int p[N],tot=0;
stack<int> sta;
void insert(int val)
{
p[++tot]=val;
int i=tot;
while(!sta.empty()&&p[sta.top()]>p[i]) sta.pop();
if(!sta.empty())
fa[i]=sta.top(),rs[sta.top()]=i,ls[i]=i-1;
else ls[i]=rt,rt=i;
sta.push(i);
}
struct RMQ
{
int L,R,dep[10015],sz[10015],ans;
int dfs1(int u)
{
dep[u]=dep[fa[u]]+1;
if(ls[u]) dfs1(ls[u]);
if(rs[u]) dfs1(rs[u]);
sz[u]+=sz[ls[u]],sz[u]+=sz[rs[u]];
}//lca(l,r)=min(val_l,val_r),dfs1->get_dep
RMQ(int l,int r):L(l),R(r){memset(dep,0,sizeof dep),memset(sz,0,sizeof sz);};
int get_RMQ(void)
{
int l=L,r=R;dfs1(1);
int u=l,v=r;
while(dep[u]!=dep[v])
{
if(dep[u]<dep[v]) swap(u,v);
u=fa[u];
}
ans=u;
}//log_2 n
};
int a[N];
int main(void)
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
build(a);
long long ans1=0,ans2=0;
for(int i=1;i<=n;i++) ans1^=1ll*i*(ls[i]+1),ans2^=1ll*i*(rs[i]+1);
printf("%lld %lld",ans1,ans2);
return 0;
}
[P4755 Beautiful Pair](P4755 Beautiful Pair - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
有一个数列\({a}\),需要求出有多少数对\((i,j)\)满足\(a_i \times a_j \le \max_{l=i}^j{a_l}\)的数量
有很多人使用的都是线段树分治,但是提到笛卡尔树了,就写一下笛卡尔树分治
笛卡尔树在这些区间最值的地方有着非常不错的性质,考虑分治,区间为\([l,r]\),\(mid=(l+r)/2\),先转化一下式子为\(a_i\le \lfloor \frac{a_{mid}}{a_j} \rfloor\),笛卡尔树满足堆的性质,也满足搜索树的性质,套个\(cdq\)分治
建出笛卡尔树,可以很容易发现,贡献都是\(max\)两边提供的,考虑两边对答案的影响:
1.max的左子树的贡献
2.max的右子树的贡献
3.右边对左边的贡献
再维护一个树状数组
时间复杂度为\(O(n log^2 n)\)
#include"bits/stdc++.h"
using namespace std;
const int N=1e5+15,M=1e9+15;
#define inl inline
#define regi register
#define PII pair<int,int>
#define int long long
inl int read(void)
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
int rt;
struct node
{
int ls,rs;
}tr[N];
int n;
void build(int* a)
{
stack<int> sta;stack<int>().swap(sta);
for(int i=1;i<=n;i++)
{
int j=0;
while(!sta.empty()&&a[sta.top()]<a[i]) j=sta.top(),sta.pop();
if(sta.empty()) rt=i;
else tr[sta.top()].rs=i;
tr[i].ls=j;
sta.push(i);
}
}
int ans;
int siz,a[N],b[N];
long long c[N];
#define lowbit(x) x&(-x)
void add(int x,int k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
int query(int x){long long res=0;for(;x;x-=lowbit(x))res+=c[x];return res;}
void solve(int u,int l,int r)
{
if(u==0) return ;
int ls=tr[u].ls,rs=tr[u].rs;
int mid=u;
if(mid-l>r-mid)
{
for(int i=mid;i<=r;i++)
{
int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
if(x) ans-=query(x-1);
}
solve(ls,l,mid-1),add(a[mid],1);
for(int i=mid;i<=r;i++)
{
int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
if(x) ans+=query(x-1);
}
solve(rs,mid+1,r);
}
else
{
for(int i=l;i<=mid;i++)
{
int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
if(x) ans-=query(x-1);
}
solve(rs,mid+1,r),add(a[mid],1);
for(int i=l;i<=mid;i++)
{
int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
if(x) ans+=query(x-1);
}
solve(ls,l,mid-1);
}
}
signed main(void)
{
n=read();
for(int i=1;i<=n;i++) b[i]=a[i]=read();
sort(b+1,b+1+n);
siz=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+siz,a[i])-b;
build(a);
solve(rt,1,n);
printf("%lld",ans);
return 0;
}