牛客网真题-71-选区间

时间复杂度O(nlogn)

我觉得大家的方案都有点太麻烦了……
观察目标函数：区间中的最小数*区间所有数的和
第一反应就是按照值从小到大处理点，这样的话区间中的最小数*就已知了，我们只用考虑区间就行。

那么，区间有多大呢？
其实题目中又一个很强的约束

区间内的所有数字都在[0, 100]的范围内;

因此区间自然是越大越好，具体来说，向左延伸到比他小的数字，向右延伸到比它小的数字。
换个角度来说：我们插入的点把区间切成两半了，每次处理新的点时，我们只需要获取它当前的区间就行。

那么如何获取区间呢？
显然的，右端点：最小的比它大的切分点,左端点：最大的比它小的切分点
平衡二叉树的经典使用场景。

时间复杂度

```
#include

vector<int> points[101];
int n,d;
scanf("%d",&n);
// 区间(b,a]的和=sum[a]-sum[b]
auto sum=new long long int[n+1];
sum[0]=0;
for (auto i=0;i<n;++i) { scanf("%d",&d); points[d].push_back(i); sum[i+1]="sum[i]+d;" } segmentation保存了已存在的分割点 map<int,bool> segmentation;
segmentation[-1]=true;segmentation[n]=true;
long long ans=0;
for (auto bid=0;bid<=100;++bid){
    for (auto p:points[bid])
    {
        //O(logn)查询区间端点
        auto itr=segmentation.upper_bound(p);
        int r=itr->first;
        --itr;
        int l=itr->first;
        //计算答案
        ans=max(ans,bid*(sum[r]-sum[l+1]));
        //插入新的切分点
        segmentation[p]=true;
    }
}
printf("%lld",ans);

}
```</n;++i)>