这个分治不好想,看的这篇题解
首先我们把(a[j]+a[i])*(j-i)转换成(a[j]-b[i])*(j-i) //b[i]=-a[i]
那么此时就变成了左下点b和右上点a求矩形的最大面积
下面是两个性质
1.如果i<j同时a[i]<a[j],那么能使a[i]最大的左下点能让a[j]更大,对b也有对偶的性质.我们先去掉无意义的点
2.(1)如果i<j,并且能使a[j]最大的左下点为k,那么能使a[i]最大的左下点的横坐标一定小于等于k
(2)如果i<j,并且能使a[i]最大的左下点为k,那么能使a[j]最大的左下点的横坐标一定大于等于k
性质1显然
证明2用反证法,如图
考虑到上面两个性质,然后...下一步需要考虑到怎么来进行优化.
因为性质二,然后就用分治解决了?!
考虑现在是al-ar,bl-br的一个区间.我们可以计算出mid=(al+ar)/2,要使a[mid]面积最大时的面积ans以及左下点b的下标pos
那么由于性质2,我们对于小于mid的点只需计算bl-pos的即可,对于大于mid的点,只需计算pos,br的即可.然后和ans比较最大值即可
查看代码
#pragma GCC optimize(2)
#include<iostream>
#include<vector>
#include<cstring>
#define ll long long
using namespace std;
ll n,cnt1,cnt2;
pair<ll,ll>a[1000005],b[1000005];
bool del[1000005];
ll cal(ll i,ll j)
{
return (a[i].second-b[j].second)*(a[i].first-b[j].first);
}
ll solve(ll al,ll ar,ll bl ,ll br)
{
if(al>ar||bl>br)return 0;
ll mid=(al+ar)>>1,ans=cal(mid,bl),pos=bl;
for(int i=bl+1;i<=br&&a[mid].first>b[i].first;i++)
{
ll tmp=cal(mid,i);
if(ans<=tmp)
{
ans=tmp;
pos=i;
}
}
return max(ans,max(solve(al,mid-1,bl,pos),solve(mid+1,ar,pos,br)));
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);//不开优化过不去
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].second;
a[i].first=i;
b[i]=a[i];
b[i].second*=-1;
}
//去掉无用点
ll last=a[n].second;
for(int i=n-1;i>0;i--)
{
if(a[i].second<=last)del[i]=1;
else last=max(last,a[i].second);
}
for(int i=1;i<=n;i++)
if(!del[i])
a[++cnt1]=a[i];
memset(del,0,sizeof(del));
last=b[1].second;
for(int i=2;i<=n;i++)
{
if(b[i].second>=last)del[i]=1;
else last=min(last,b[i].second);
}
for(int i=1;i<=n;i++)
if(!del[i])b[++cnt2]=b[i];
cout<<solve(1,cnt1,1,cnt2);
return 0;
}