赛克oj The diameter of a rectangle（笛卡尔树）

赛氪OJ-专注于算法竞赛的在线评测系统 (saikr.com)

这题是hduoj 1506的加强版，区别在于宽度不是固定为1了，思路差不多，也是使用笛卡尔树。参考hduoj 1506（笛卡尔树） - Venux - 博客园 (cnblogs.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 ll a[N],b[N];
17 int st[N],ls[N],rs[N];
18 ll ans;
19 ll dfs(int u){
20     if(!u)return 0;
21     ll res=dfs(ls[u])+dfs(rs[u])+b[u];
22     ll res1=min(res,a[u]);
23     res1*=res1;
24     ans=max(ans,res1);
25     return res;
26 }
27 int main(){
28     IO;
29     
30     cin>>n;
31         
32     for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
33     int h=0;
34     for(int i=1;i<=n;i++){
35         int k=h;
36         while(k>0&&a[st[k]]>a[i])k--;
37         if(k>0)rs[st[k]]=i;
38         if(k<h) ls[i]=st[k+1];
39         st[++k]=i;
40         h=k;
41     }
42     //bug(st[1]);
43     ans=0;
44     dfs(st[1]);
45     cout<<ans<<endl;
46     
47 }
48 /*
49 11
50 9 3 7 1 8 12 10 20 15 18 5
51 
52 */