Cartesian_tree 学习笔记

## 说在前面 由于作者是一个初二蒟蒻，有一些地方可能存在问题，请多指教。喷轻点。 我与 $ZXJ$ 大佬是同学（我就是他口中的 $LCX$ 蒟蒻），这里顺便推荐一下他以前的日报[浅谈牛顿迭代法](https://www.luogu.com.cn/blog/zhang-xu-jia/niu-dun-die-dai-fa-yang-xie)（虽然有些图咕掉了）。 当然还有一篇已经过了但被管理员咕掉的日报[浅谈几种插值方法](https://www.luogu.com.cn/blog/zhang-xu-jia/ji-zhong-cha-zhi-fang-fa-yang-xie)，由于 $ZXJ$ 大佬正在补文化课，所以不常上洛谷，麻烦管理员看到这篇日报后，恢复一下 $ZXJ$ 大佬的日报（如果日报内容存在问题，可私信我，让我转告）。 upd 2020.9.20： ~~好像已经解决了……~~ 在很久很久以前，有一道~~大难~~题诞生了…… ## ~~毫无违和感地直接引入~~例题1 HDU 1506 最大子矩形 题目大意：$n$ 个位置，每个位置上的高度是 $h_i$，求最大子矩阵。举一个例子，如下图：  阴影部分就是图中的最大子矩阵。 大佬 $XWW$ （即在我日报后的日报[浅谈ZKP问题](https://www.luogu.com.cn/blog/53533/qian-tan-zkp-wen-ti-gai-post)的作者）跑过来说：“这是一道水题，$DP+$ 单调栈维护一下就过了。” 的确，这道题十分的简单，一个 $DP$ 就可以轻松解决。 然后这道题就被解决了。 $$$$ $$\Huge\color{purple}\text{完结撒花！！！}$$ $$$$ 读者：“作者你是不是找死！” 作者：“疼疼疼，别扔鸡蛋了，鸡蛋很贵的！” 这道题真的解决了吗？对于我这样的 $DP$ 蒟蒻来说，这道题就算打出来了，过了几个月也还是不会啊。 难道就没有简单一点的算法？ ## ~~没有~~ 读者：“作者你是不是又找死！” 作者：“疼疼疼，别扔鸡蛋了，我正经一点还不行吗！” 经过几~~万~~年的时间，一个算法横空出世了！ **它是一个与平衡树和堆密切相关的数据结构。** **它在操作少和数据随机的情况下能很好的解决一些区间最值问题。** **它就是——** # 笛卡尔树。 那~~为了不让读者再次向我扔鸡蛋~~，我们就开始打开笛卡尔树的大门吧。 ## 笛卡尔树的简介 ```cpp 笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、 范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。 笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。 从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。 ——摘自百度百科 ``` 读了上述文字，相信你对笛卡尔树有了一定的了解。也知道了它的用处。那么一棵笛卡尔树怎么构造呢？ 我们先来看一棵笛卡尔树。  观察这一棵笛卡尔树，你发现了什么？ ## 笛卡尔树的定义及性质 我们定义，数组的元素值当做键值 $w$，数组的下标当做键值 $k$，那么 $w$ 和 $k$ 构成了一个二元组。 对于一个无重复元素的笛卡尔树（如上图）有以下性质。 $1$、$w$ 在树中满足堆的性质，而 $k$ 满足二叉搜索树的性质。 $2$、中序遍历笛卡尔树可以得到原序列。 $3$、结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素。 这三个性质定义了一棵笛卡尔树。 其实图中的笛卡尔树是一种特殊的情况，因为二元组的键值恰好对应数组下标。 这种特殊的笛卡尔树有一个性质，就是一棵子树内的下标是连续的一个区间（因为下标满足二叉搜索树的性质）。 更一般的情况则是任意二元组构建的笛卡尔树。 还有一个有趣的事实：如果二元组 $(k,w)$ 中的 $k$ 互不相同，$w$ 也互不相同，那么它构成的笛卡尔树的结构是唯一的。 ## 笛卡尔树的构造 上面我们已经得到了笛卡尔树的两个性质，现在我们就来讲讲它的构造方法。 首先按照键值 $k$ 排序，然后按顺序插入到这颗树的右链（从根节点一直走右儿子的链）中以满足 $k$ 的性质，维护数的性质。图中红色框表示右链。    插入一个 $9$。 插入一个 $3$，发现不符合堆的性质，与父亲交换一下，更新右链。 插入一个 $7$。   插入一个 $1$，发现不符合堆的性质，与父亲交换一下，发现还不符合堆的性质，再与父亲交换一下，更新右链。 插入一个 $8$。   插入一个 $12$。 插入一个 $10$，发现不符合堆的性质，与父亲交换一下。   插入一个 $20$。 插入一个 $15$，发现不符合堆的性质，与父亲交换一下。  插入一个 $18$。  插入一个 $5$，一直与父亲交换，使得满足堆的性质。  最后一棵笛卡尔树就建成了。 然后我们观察一下构造整个笛卡尔树的过程，会发现，每个节点只会进出右链一次，那么，我们用一个单调栈来维护这个右链的状态，就可以轻松搞定啦。 ## $code$ ```cpp for (int i=1;i<=n;i++) { int k=top;//top表示操作前栈顶，k表示操作中栈顶 while (k>0&&h[stk[k]]>h[i]) k--; if (k) rs[stk[k]]=i; //rs代表笛卡尔树每个节点的右儿子 //栈未空，栈顶右儿子等于当前元素 if (k<top) ls[i]=stk[k+1]; //ls代表笛卡尔树每个节点的左儿子 //退了栈，当前元素左儿子等于前一个退栈元素 stk[++k]=i;//当前元素入栈 top=k; } ``` 时间复杂度：$O(n)$。 然后你们就可以 $A$ 了这道题——[P5854 【模板】笛卡尔树](https://www.luogu.com.cn/problem/P5854) ~~祝你们好运！~~ ## 让我们~~再次毫无违和感地~~回到例题1 HDU 1506 最大子矩形 题目大意：$n$ 个位置，每个位置上的高度是 $h_i$，求最大子矩阵。举一个例子，如下图：  我们将下标当做键值 $k$，$h_i$当做键值 $w$。那么根据笛卡尔树的性质，可以得出，对于一个节点，它子树内的节点在原序列是一段连续的区间，而且 $h$ 都比这个节点的 $h$ 大，所以我们就可以枚举每个节点，把这个节点的 $h$ 当做矩形的高度，而这个节点子树内的所有节点都可以加入这个矩形。然后算出的答案与最大值比较即可。 这道题还是比较简单的，代码部分就交给读者们啦。 ## 例题2 [P3246 [HNOI2016]序列](https://www.luogu.org/problem/P3246) 这道题的题目大意就是说，给你 $m$ 个数，然后给你一个区间 $l$~$r$，让你求这个区间里的所有子序列的最小值之和。 ## 题解 虽然这道题可以离线莫队做，但是我们这里只讲笛卡尔树的做法。 首先 $O(n)$ 构造一个笛卡尔树。 设 $f[i][j]$ 表示以 $i$ 为右端点，左端点在 $i$~$j$ 之间的答案。 考虑从 $f[i][j]$ 转移到 $f[i][j+1]$。 设 $last[i]$ 表示在 $i$ 前面，比 $a[i]$ 大的第一个数的位置。 那么 $last[j]+1$~$j$ 这段区间中的最小值都是 $a[j]$。 就有转移 $f[i][j]=f[i][last[j]]+a[j]\times(j-last[j])$。 我们发现 $DP$ 的增量与 $i$ 无关，可以去掉那一维。 得到 $f[i]=f[last[i]]+a[i]\times(i-last[i])$。 然后对它做一个前缀和，设为 $g$。 我们回到原来的问题。 设 $p$ 为 $l$~$r$ 的最小值的位置。 那么如果子区间跨过 $p$，贡献就是 $a[p]$。 所以这一段的贡献就是 $a[p]\times(p-l+1)\times(r-p+1)$，也就是左端点有 $p-l+1$ 个，右端点有 $r-p+1$ 个，然后任意组合。 剩下考虑 $p$~$r$ 的贡献，也就是 $g[r]-g[p]-f[p]*(r-p)$，也就是右端点为 $p$~$r$ 的贡献，然后同时规定左端点必须在 $p$ 之后，所以要减去 $f[p]*(r-p)$。 对于 $l$~$p$ 的贡献，我们同样设一个类似 $f$ 的 $DP$ ，然后统计一个后缀和算贡献即可。 有人就会问了，那我们一开始建立笛卡尔树干什么呢？ 还记得 $p$ 吗，它是 $l$~$r$ 区间的最小值，如果用 $ST$ 表就只能跑到 $n\;\log\;n$，但如果我们在笛卡尔树上查询的话，虽然一次查询上界是 $O(n)$ 的，但是笛卡尔树本来就是针对随机数据的，所以直接暴力往下找即可，而且跑得很快。 ## $code$ ```cpp #include<cstdio> using namespace std; int a[100001],ls[100001],rs[100001],s[100001],top,n,rt,last[100001]; int next[100001],m,l,r; long long fr[100001],fl[100001],gr[100001],gl[100001]; int query(int l,int r) { for (int i=rt;;i=i>r?ls[i]:rs[i]) if (l<=i&&i<=r) return i; } int main() { scanf("%d%d",&n,&m);a[0]=a[n+1]=0x3f3f3f3f; for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) { int k=top; while (k>0&&a[s[k]]>a[i]) k--; if (k) rs[s[k]]=i; if (k<top) ls[i]=s[k+1]; s[++k]=i; top=k; } rt=s[1],top=0; for (int i=1;i<=n;i++) { while(top&&a[s[top]]>a[i]) next[s[top--]]=i; last[i]=s[top],s[++top]=i; } while(top) last[s[top]]=s[top-1],next[s[top--]]=n+1; for (int i=1;i<=n;i++) fr[i]=fr[last[i]]+1ll*a[i]*(i-last[i]),gr[i]=gr[i-1]+fr[i]; for (int i=n;i>=1;i--) fl[i]=fl[next[i]]+1ll*a[i]*(next[i]-i),gl[i]=gl[i+1]+fl[i]; for (int i=1;i<=m;i++) { scanf("%d%d",&l,&r); int p=query(l,r); printf("%lld\n",1ll*(p-l+1)*(r-p+1)*a[p]+gr[r]-gr[p]-fr[p]*(r-p)+gl[l]-gl[p]-1ll*fl[p]*(p-l)); } return 0; } ``` ## 例题3 [P4755 Beautiful Pair](https://www.luogu.org/problem/P4755) ## 题解 建一棵笛卡尔树。 考虑在笛卡尔树上分治。 假设我们当前分治到区间 $l$~$r$，当前笛卡尔树上的节点在原序列上的编号是 $pos$。 根据分治套路，我们只需要计算跨过 $pos$ 的答案，然后 $l$~$pos-1$ 和 $pos+1$~$r$ 分治处理。 我们来看看跨过 $pos$ 的贡献怎么算。 首先启发式分裂一下，如果 $pos-l$ 比 $r-pos$ 要小的话，我们就枚举左边，然后去算右边的贡献，否则反之，这样可以减少时间复杂度。 我们这里只讲枚举左边去算右边的贡献的情况，另一种同理。 枚举点对的左端点，由于 $l$~$r$ 的最大值是 $a[pos]$ ，所以右端点的值要比 $\frac{a[pos]}{a[l]}$ 小，这种区间求比某个数小的数量可以用主席树来实现。 $a[i]$ 比较大，所以离散化一下。 ## $code$ ```cpp #include<cstdio> #include<algorithm> using namespace std; int n,a[100001],b[100001],top,len,rt,root[100001],ls[100001],tot; int rs[100001],stk[100001]; long long ans; struct node{int l,r,sum;} tree[2000001]; int get(int x) {return lower_bound(b+1,b+len+1,x)-b;} void change(int &rt,int k,int l,int r,int x) { if(l>x||r<x) return; rt=++tot; tree[rt].sum=tree[k].sum+1; tree[rt].l=tree[k].l; tree[rt].r=tree[k].r; if(l==r) return; int mid=(l+r)>>1; change(tree[rt].l,tree[k].l,l,mid,x); change(tree[rt].r,tree[k].r,mid+1,r,x); } int query(int rt,int k,int l,int r,int x) { if(l>x) return 0; if(r<=x) return tree[rt].sum-tree[k].sum; int mid=l+r>>1,ret=0; ret+=query(tree[rt].l,tree[k].l,l,mid,x); ret+=query(tree[rt].r,tree[k].r,mid+1,r,x); return ret; } void solve(int l,int r,int pos) { if(l>r)return; if(l==r){ans+=(b[a[l]]==1);return;} if(pos-l+1<=r-pos) for(int i=l;i<=pos;i++) { int k=upper_bound(b+1,b+len+1,b[a[pos]]/b[a[i]])-b-1; ans+=query(root[r],root[pos-1],1,len,k); } else for(int i=pos;i<=r;i++) { int k=upper_bound(b+1,b+len+1,b[a[pos]]/b[a[i]])-b-1; ans+=query(root[pos],root[l-1],1,len,k); } solve(l,pos-1,ls[pos]);solve(pos+1,r,rs[pos]); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); len=unique(b+1,b+n+1)-b-1; for (int i=1;i<=n;i++) { int k=top; while (k>0&&a[stk[k]]<a[i]) k--; if (k) rs[stk[k]]=i; if (k<top) ls[i]=stk[k+1]; stk[++k]=i; top=k; } rt=stk[1]; for (int i=1;i<=n;i++) a[i]=get(a[i]); for (int i=1;i<=n;i++) change(root[i],root[i-1],1,len,a[i]); solve(1,n,rt); printf("%lld",ans); return 0; } ``` $$$$ $$$$ $$\Huge\color{purple}\text{完结撒花！！！}$$ $$$$ $$$$ ## 其他习题 [P2611 [ZJOI2012]小蓝的好友](https://www.luogu.org/problem/P2611) [P5044 [IOI2018] meetings 会议](https://www.luogu.org/problem/P5044) 其他平衡树的题大佬们也可以去做做（感谢@万万没想到 的提醒） ## 课后思考 其实标准 $RMQ$ 也是通过笛卡尔树实现的（当然还加上别的算法），大家可以去研究一下。 ## 说在后面 感谢一些学术网站以及一些大佬的博客，在这里可能引用了他们的图和题，这里声明一下.（感谢@BoringHacker 的提醒） [OI wiki](https://oi-wiki.org/ds/cartesian-tree/) [大佬的博客](https://www.cnblogs.com/LiuRunky/p/Cartesian_Tree.html) [大佬的博客2](https://blog.csdn.net/qq_39898877/article/details/97690031) upd 2020.08.07：做一个小小的统计