hduoj 1506（笛卡尔树）

Problem - 1506 (hdu.edu.cn)

题意

坐标轴给定一些矩形，紧密排在一起，每个矩形宽度固定为1，问形成的图案中最大可以组成的矩形面积。

思路

常规思路是可以用单调栈分别找两边的合法边界，这里使用笛卡尔树。笛卡尔树实现了堆的性质，并且对原数组建立的笛卡尔树进行中序遍历为原数组的顺序，所以可以方便进行此类区间操作。详细可以参考笛卡尔树 - 知乎 (zhihu.com)

 1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 2 #define bug(x) cout<<#x<<" is "<<x<<endl
 3 #include <bits/stdc++.h>
 4 #define iter ::iterator
 5 using namespace  std;
 6 typedef long long ll;
 7 typedef pair<int,int>P;
 8 #define pb push_back
 9 #define mk make_pair
10 #define se second
11 #define fi first
12 // #define rs o*2+1
13 // #define ls o*2
14 const int N=1e5+5;
15 int n;
16 int a[N];
17 int st[N],ls[N],rs[N];
18 ll ans;
19 int dfs(int u){
20     if(!u)return 0;
21     int res=dfs(ls[u])+dfs(rs[u])+1;
22     ans=max(ans,1ll*a[u]*res);
23     return res;
24 }
25 int main(){
26     IO;
27     while(cin>>n){
28         if(n==0)return 0;
29         for(int i=1;i<=n;i++)cin>>a[i],ls[i]=rs[i]=0;
30         int h=0;
31         for(int i=1;i<=n;i++){
32             int k=h;
33             while(k>0&&a[st[k]]>a[i])k--;
34             if(k>0)rs[st[k]]=i;
35             if(k<h) ls[i]=st[k+1];
36             st[++k]=i;
37             h=k;
38         }
39         //bug(st[1]);
40         ans=0;
41         dfs(st[1]);
42         cout<<ans<<endl;
43     }
44 }
45 /*
46 11
47 9 3 7 1 8 12 10 20 15 18 5
48 
49 */