题意:

求max(min(a[i]..a[j])*(j-i+1))

多测,n<=100000

链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1985

解法:

一颗简单的线段树

据说还有别的神奇的O(n)的做法?

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100005];
int val[1<<18];
int l_max[1<<18];
int r_max[1<<18];
struct node
{
    int loc;
    int num;
    friend bool operator < (const node &a,const node &b)
    {
        return a.num<b.num;
    }
};
node b[100005];
void change(int num,int l,int r,int k)
{
    if (l==r-1)
    {
        val[num]=1;
        r_max[num]=1;
        l_max[num]=1;
        return;
    }
    int mid=(l+r)/2;
    if (k<mid)
    {
        change(num*2+1,l,mid,k);
    }
    else
    {
        change(num*2+2,mid,r,k);
    }
    l_max[num]=l_max[num*2+1];
    if (l_max[num*2+1]==(mid-l)) l_max[num]+=l_max[num*2+2];
    r_max[num]=r_max[num*2+2];
    if (r_max[num*2+2]==(r-mid)) r_max[num]+=r_max[num*2+1];
    val[num]=max(r_max[num*2+1]+l_max[num*2+2],max(val[num*2+1],val[num*2+2]));
}
int query(int num,int l,int r)
{
    return val[num];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    for (;;)
    {
        scanf("%d",&n);
        if (n==0) break;
        int i;
        for (i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            b[i].loc=i;
            b[i].num=a[i];
        }
        memset(val,0,sizeof(val));
        memset(r_max,0,sizeof(r_max));
        memset(l_max,0,sizeof(l_max));
        sort(b,b+n);
        long long max_ans=0;
        for (i=n-1;i>=0;i--)
        {
            change(0,0,n,b[i].loc);
            max_ans=max(max_ans,query(0,0,n)*(long long)b[i].num);
        }
        cout<<max_ans<<'\n';
    }
    return 0;
}