说在前面

由于作者是一个初二蒟蒻，有一些地方可能存在问题，请多指教。喷轻点。

我与 ZXJ 大佬是同学（我就是他口中的 LCX 蒟蒻），这里顺便推荐一下他以前的日报浅谈牛顿迭代法（虽然有些图咕掉了）。

当然还有一篇已经过了但被管理员咕掉的日报浅谈几种插值方法，由于 ZXJ 大佬正在补文化课，所以不常上洛谷，麻烦管理员看到这篇日报后，恢复一下 ZXJ 大佬的日报（如果日报内容存在问题，可私信我，让我转告）。

upd 2020.9.20： 好像已经解决了……

在很久很久以前，有一道大难题诞生了……

毫无违和感地直接引入例题1

HDU 1506 最大子矩形

题目大意：n 个位置，每个位置上的高度是 h_i，求最大子矩阵。举一个例子，如下图：

阴影部分就是图中的最大子矩阵。

大佬 XWW （即在我日报后的日报浅谈ZKP问题的作者）跑过来说：“这是一道水题，DP+ 单调栈维护一下就过了。”

的确，这道题十分的简单，一个 DP 就可以轻松解决。

然后这道题就被解决了。

$$\Huge\color{purple}\text{完结撒花！！！}$$

读者：“作者你是不是找死！”

作者：“疼疼疼，别扔鸡蛋了，鸡蛋很贵的！”

这道题真的解决了吗？对于我这样的 DP 蒟蒻来说，这道题就算打出来了，过了几个月也还是不会啊。

难道就没有简单一点的算法？

没有

读者：“作者你是不是又找死！”

作者：“疼疼疼，别扔鸡蛋了，我正经一点还不行吗！”

经过几万年的时间，一个算法横空出世了！

它是一个与平衡树和堆密切相关的数据结构。

它在操作少和数据随机的情况下能很好的解决一些区间最值问题。

它就是——

笛卡尔树。

那为了不让读者再次向我扔鸡蛋，我们就开始打开笛卡尔树的大门吧。

笛卡尔树的简介

笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、

范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。

笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。

从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。
                                                                                ——摘自百度百科

读了上述文字，相信你对笛卡尔树有了一定的了解。也知道了它的用处。那么一棵笛卡尔树怎么构造呢？

我们先来看一棵笛卡尔树。

观察这一棵笛卡尔树，你发现了什么？

笛卡尔树的定义及性质

我们定义，数组的元素值当做键值 w，数组的下标当做键值 k，那么 w 和 k 构成了一个二元组。

对于一个无重复元素的笛卡尔树（如上图）有以下性质。

$2$、中序遍历笛卡尔树可以得到原序列。 $3$、结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素。 这三个性质定义了一棵笛卡尔树。 其实图中的笛卡尔树是一种特殊的情况，因为二元组的键值恰好对应数组下标。 这种特殊的笛卡尔树有一个性质，就是一棵子树内的下标是连续的一个区间（因为下标满足二叉搜索树的性质）。 更一般的情况则是任意二元组构建的笛卡尔树。 还有一个有趣的事实：如果二元组 $(k,w)$ 中的 $k$ 互不相同，$w$ 也互不相同，那么它构成的笛卡尔树的结构是唯一的。 ## 笛卡尔树的构造 上面我们已经得到了笛卡尔树的两个性质，现在我们就来讲讲它的构造方法。 首先按照键值 $k$ 排序，然后按顺序插入到这颗树的右链（从根节点一直走右儿子的链）中以满足 $k$ 的性质，维护数的性质。图中红色框表示右链。    插入一个 $9$。 插入一个 $3$，发现不符合堆的性质，与父亲交换一下，更新右链。 插入一个 $7$。   插入一个 $1$，发现不符合堆的性质，与父亲交换一下，发现还不符合堆的性质，再与父亲交换一下，更新右链。 插入一个 $8$。   插入一个 $12$。 插入一个 $10$，发现不符合堆的性质，与父亲交换一下。   插入一个 $20$。 插入一个 $15$，发现不符合堆的性质，与父亲交换一下。  插入一个 $18$。  插入一个 $5$，一直与父亲交换，使得满足堆的性质。  最后一棵笛卡尔树就建成了。 然后我们观察一下构造整个笛卡尔树的过程，会发现，每个节点只会进出右链一次，那么，我们用一个单调栈来维护这个右链的状态，就可以轻松搞定啦。 ## $code

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 【模板】笛卡尔树

祝你们好运！

让我们再次毫无违和感地回到例题1

HDU 1506 最大子矩形

题目大意：n 个位置，每个位置上的高度是 h_i，求最大子矩阵。举一个例子，如下图：

我们将下标当做键值 k，h_i当做键值 w。那么根据笛卡尔树的性质，可以得出，对于一个节点，它子树内的节点在原序列是一段连续的区间，而且 h 都比这个节点的 h 大，所以我们就可以枚举每个节点，把这个节点的 h 当做矩形的高度，而这个节点子树内的所有节点都可以加入这个矩形。然后算出的答案与最大值比较即可。

这道题还是比较简单的，代码部分就交给读者们啦。

例题2

P3246 [HNOI2016]序列

这道题的题目大意就是说，给你 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

#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

题解

建一棵笛卡尔树。

考虑在笛卡尔树上分治。

假设我们当前分治到区间 l~r，当前笛卡尔树上的节点在原序列上的编号是 pos。

根据分治套路，我们只需要计算跨过 pos 的答案，然后 l~pos-1 和 pos+1~r 分治处理。

我们来看看跨过 pos 的贡献怎么算。

首先启发式分裂一下，如果 pos-l 比 r-pos 要小的话，我们就枚举左边，然后去算右边的贡献，否则反之，这样可以减少时间复杂度。

我们这里只讲枚举左边去算右边的贡献的情况，另一种同理。

枚举点对的左端点，由于 l~r 的最大值是 a[pos] ，所以右端点的值要比 \frac{a[pos]}{a[l]} 小，这种区间求比某个数小的数量可以用主席树来实现。

## $code

#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]小蓝的好友

P5044 [IOI2018] meetings 会议

其他平衡树的题大佬们也可以去做做（感谢@万万没想到 的提醒）

课后思考

其实标准 RMQ 也是通过笛卡尔树实现的（当然还加上别的算法），大家可以去研究一下。

说在后面

感谢一些学术网站以及一些大佬的博客，在这里可能引用了他们的图和题，这里声明一下.（感谢@BoringHacker 的提醒）

OI wiki

大佬的博客

大佬的博客2

upd 2020.08.07：做一个小小的统计