题目: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=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } ll Mx(ll a,ll b){return a>b?a:b;} const int N=1e5+5; int n,a[N],sta[N],top,ls[N],rs[N],fa[N];ll ans; int dfs(int cr) { if(!cr)return 0; int siz=dfs(ls[cr])+dfs(rs[cr])+1; ans=Mx(ans,(ll)siz*a[cr]); return siz; } void get_dkr() { top=0; for(int i=1;i<=n;i++) { ls[i]=rs[i]=fa[i]=0; 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(1) { n=rdn();if(!n)break; for(int i=1;i<=n;i++)a[i]=rdn(); get_dkr(); ans=0; dfs(rs[0]); printf("%lld\n",ans); } return 0; }