hdu 1506 Largest Rectangle in a Histogram——笛卡尔树

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1506

关于笛卡尔树的构建：https://www.cnblogs.com/reverymoon/p/9525764.html

笛卡尔树在 key 上满足二叉搜索树，在 value 上满足堆；一般 key 就是原序列里的位置，这样一个子树对应原序列的一段连续区间。

这个构建方法就是给最右链维护单调栈，新进来第 i 个元素之后，根据 value 是堆的规则弹栈，然后把自己的左孩子设成最后弹掉的那个点，把自己的父亲设作那个点原本的父亲；自己充当那个点原本父亲的右孩子。

这也是 O(n) 建堆/treap的方法。

关于笛卡尔树的合并：https://www.cnblogs.com/Miracevin/p/10373626.html

本题建一个小根堆，每个点的高度 * 子树 size 可以贡献给答案。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Mx(ll a,ll b){return a>b?a:b;}

const int N=1e5+;

int n,a[N],sta[N],top,ls[N],rs[N],fa[N];ll ans;

int dfs(int cr)

{

  if(!cr)return ;

  int siz=dfs(ls[cr])+dfs(rs[cr])+;

  ans=Mx(ans,(ll)siz*a[cr]);

  return siz;

}

void get_dkr()

{

  top=;

  for(int i=;i<=n;i++)

    {

      ls[i]=rs[i]=fa[i]=;

      while(top&&a[sta[top]]>=a[i])

    ls[i]=sta[top--];

      fa[i]=sta[top]; sta[++top]=i;

      rs[fa[i]]=i; if(ls[i])fa[ls[i]]=i;

    }

}

int main()

{

  while()

    {

      n=rdn();if(!n)break;

      for(int i=;i<=n;i++)a[i]=rdn();

      get_dkr(); ans=; dfs(rs[]);

      printf("%lld\n",ans);

    }

  return ;

}