区间的价值 51Nod - 1564

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1564

想了半天没什么好想法 一看题解就是个暴力。。

说是个分治很好听 但是这样处理的区间其实就是用单调栈找出的每个最值区间的左右端点 就和对这些区间分别暴力找最大值是一模一样的 有一个等差数列直接变n^2 到了赛场上哪有那么多随机数据给你暴力去

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int N=0x3f3f3f3f;

ll ary[maxn],ans[maxn];
int n;

void solve(int l,int r)
{
    ll minn,maxx;
    int i,p1,p2;
    if(l>r) return;
    minn=N,maxx=0;
    for(i=l;i<=r;i++){
        if(minn>ary[i]) minn=ary[i],p1=i;
        if(maxx<ary[i]) maxx=ary[i],p2=i;
    }
    for(i=abs(p1-p2+1);i<=r-l+1;i++) ans[i]=max(ans[i],minn*maxx);
    solve(l,p1-1);
    solve(p1+1,r);
}

int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%lld",&ary[i]);
    solve(1,n);
    for(i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}