本文共 1295 字，大约阅读时间需要 4 分钟。

定义

笛卡尔树是一种key的二叉搜索树，val的小顶堆，Treap是特殊的笛卡尔树。如图，中序排序为key(此处为序列下标)的升序排列，且父节点的val小于子节点的val。

构造

使用栈始终维护以根节点为开始的右链。按key从小到大依次入栈。加入点u时，找到栈中第一个val小于val[u]的点x。把x的右儿子变成点u的左儿子，点u作为点x的右儿子。(保持中序遍历key有序)。

应用

#include 
   
    #define debug(__x,_ge) cout<<#__x<<"="<<__x<<_ge#define endl '\n'using namespace std;using ll = long long;using pii = pair
    
     ;const int maxn = 1e5+5;struct Node{
       int idx, val, par, ch[2];}tree[maxn];int n,top;int stk[maxn];ll ans;void add(int idx){
       int k=top;    while(k && tree[stk[k]].val > tree[idx].val)        --k;    if(k!=top){
     // 不是右链最后一个        tree[idx].ch[0]=stk[k+1];        tree[stk[k+1]].par = idx;    }    if(k)tree[stk[k]].ch[1] = idx, tree[idx].par = stk[k];    stk[++k] = idx;    top = k;}int dfs(int u){
       if(!u)return 0;    int siz = dfs(tree[u].ch[0]) + dfs(tree[u].ch[1]) + 1;    ans = max(ans, ll(siz) * tree[u].val);    return siz;}int main(){
       int T;    cin.tie(0),cout.tie(0);    ios::sync_with_stdio(false);    while(cin>>n && n){
           top = 0;        ans = 0;        for(int i=1;i<=n;++i){
               cin>>tree[i].val;            tree[i].idx = i;            tree[i].par = tree[i].ch[0] = tree[i].ch[1] = 0;            add(i);        }        dfs(stk[1]);        cout<
     
      <
     
    
   

HDU

转载地址：http://qgkzi.baihongyu.com/