笛卡尔树

笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。

无相同元素的数列构造出的笛卡尔树具有下列性质：

1. 结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素
2. 中序遍历（in-order traverse）笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小，右子树结点所对应数列元素下标比该结点所对应元素下标大。
3. 树结构存在堆序性质，即任意树结点所对应数值大/小于其左、右子树内任意结点对应数值

根据堆序性质，笛卡尔树根结点为数列中的最大/小值，树本身也可以通过这一性质递归地定义：根结点为序列的最大/小值，左、右子树则对应于左右两个子序列，其结点同样为两个子序列的最大/小值。因此，上述三条性质唯一地定义了笛卡尔树。若数列中存在重复值，则可用其它排序原则为数列中相同元素排定序列，例如以下标较小的数为较小，便能为含重复值的数列构造笛卡尔树。

如图该数列就建成了一个笛卡尔树，可以观察出每个节点的左子树都是该数列的左边的值，右子树都是该数列右边值。
且每个节点的一定是它所有子树中节点数值最小的一个。

那么问题来，怎么来建该树呢？

void build(){
    stack<int> q;
    for (int i = 1; i <= n;i++){
        while(!q.empty() && a[a.top()]>a[i]){
            l[i] = q.top();
            q.pop();
        }
        if(!q.empty())
            r[q.top()] = i;
        q.push(i);
    }
    while(!q.empty())
        root = q.top(), q.pop();
}

那么笛卡尔树该怎么用呢？
都说了笛卡尔树是根据下标与值来建立的，所有如果两个函数图像递增 ，递减区间一样那么它们的笛卡尔树当然也一样。
看题：
Equivalent Prefixes
题意：给两个数列找出一个 1到p的数列使1到p的任何区间的最小值的下标相等，使p最大。
题解：要想使，1到p任何区间的数列的最小值的下标相等，也就是使两个函数图像相等。
代码 ：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int l[2][N], r[2][N], rt1,rt2;
int a[N],b[N];

void build(int n){
    stack<int> q;
    for (int i = 1; i <= n;i++){
        l[0][i] = r[0][i] = 0;
        while(!q.empty() && a[i]<a[q.top()]){
            l[0][i] = q.top();
            q.pop();
        }
        if(!q.empty())
            r[0][q.top()] = i;
        q.push(i);
    }
    while(!q.empty())
        q.pop();
    for (int i = 1; i <= n;i++){
        l[1][i] = r[1][i] = 0;
        while(!q.empty()&&b[i]<b[q.top()]){
            l[1][i] = q.top();
            q.pop();
        }
        if(!q.empty())
            r[1][q.top()] = i;
        q.push(i);
    }
    while(!q.empty())
        q.pop();
}

bool judge(int n){
    for (int i = 1; i <= n;i++){
        if(l[0][i]!=l[1][i]||r[0][i]!=r[1][i])
            return false;
    }
    return true;
}

int main(){
    int n;
    while(~scanf("%d", &n)){
        for (int i = 1; i <= n;i++){
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n;i++){
            scanf("%d", &b[i]);
        }
        int l, r, m;
        l = 1, r = n;
        while(l <= r){
            m = (l + r) / 2;
            build(m);
            if(judge(m))
                l = m+1;
            else
                r = m-1;
        }
        printf("%d\n", (l+r)/2);

    }
}

Largest Rectangle in a Histogram

题意：求一个最大子矩阵。
题解：求最大子矩阵，可以枚举每个点的高度 ，然后再找左边第一个小于它的，与右边第一个小于它的。根据笛卡尔树的性质，节点的值小于左子树 ，与右子树，而且左子树右子树又在区间连续，所以只要判断节点的子节点个数。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
int l[N],r[N],n,rt,size[N];
ll h[N], ans, maxn;

void build(){
    stack<int> q;
    for (int i = 1; i <= n; i++){
        while(!q.empty() && h[q.top()] > h[i]){
            l[i]=q.top(),q.pop();
        }
        if(!q.empty()){
            r[q.top()] = i;
        }
        q.push(i);
    }
    while(!q.empty()){
        rt = q.top();
        q.pop();
    }
}

void dfs(int u){
    if(!u){
        return;
    }
    size[u] = 1;
    dfs(l[u]);
    size[u] += size[l[u]];
    dfs(r[u]);
    size[u] += size[r[u]];
}

int main(){
    while(~scanf("%d", &n) && n){
        maxn = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &h[i]);
        }
        build();
        dfs(rt);
        for (int i = 1; i <= n;i++){
            ans = h[i] * 1ll * size[i];
            maxn = max(ans, maxn);
        }
        printf("%lld\n", maxn);
        for (int i = 1; i <= n+1;i++){
            l[i] = r[i] = 0;
        }
    }
}