Hdu5696 区间的价值

区间的价值

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1405 Accepted Submission(s): 623

Problem Description

我们定义“区间的价值”为一段区间的最大值*最小值。

一个区间左端点在

Input

多组测试数据

第一行一个数

Output

输出共

Sample Input

5 1 6 2 4 4

Sample Output

36 16 12 12 6

Source

2016"百度之星" - 初赛（Astar Round2B）

Recommend

wange2014

分析：一开始想着用单调栈+线段树来做，结果T了，极限数据要5s多一点，刚好超时QAQ.

解法是分治.因为有最大值和最小值的约束，消除一个约束：固定最小值,先找出跨过这个最小值的所有区间的答案,分别往左和往右扩展答案,记录一端恰好是最小值的区间的答案.因为已经确定了最小值，所以所有跨过这个最小值的区间的答案都是递增的,而且要求的是长度为i的答案，不要求具体的区间，所以可以用小区间的答案取更新大区间的答案.接着分治处理左半边和右半边的区间.

因为数据是随机的，不会退化到O(n^2).get到了一种新的分治技巧，有时候不必按照中点分.

下面说说我的超时思路，警戒一下后来人吧.我的想法是枚举区间的左端点，记录当前区间的最大值和最小值，并记录比当前最大值更大的下一个数的位置和更小的下一个数的位置.记上一次操作的位置为last,这一次跳到的位置为cur,那么影响到的区间长度为[last - i + 1,cur - i]，区间修改，单点查询，利用线段树维护.

TLE代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 100010;
typedef long long ll;
ll maxx[maxn << 2],a[maxn],nextmax[maxn],nextmin[maxn],sta[maxn],pos[maxn],head,cur1,cur2,tag[maxn << 2];
int n;

void init()
{
    memset(maxx,0,sizeof(maxx));
    memset(nextmax,0,sizeof(nextmax));
    memset(nextmin,0,sizeof(nextmin));
    memset(sta,0,sizeof(sta));
    memset(pos,0,sizeof(pos));
    head = 0;
    cur1 = cur2 = 0;
    memset(tag,0,sizeof(tag));
}

void pushup(int o)
{
    maxx[o] = max(maxx[o * 2],maxx[o * 2 + 1]);
}

void pushdown(int o)
{
    if (tag[o])
    {
        tag[o * 2] = max(tag[o * 2],tag[o]);
        tag[o * 2 + 1] = max(tag[o * 2 + 1],tag[o]);
        maxx[o * 2] = max(maxx[o * 2],tag[o]);
        maxx[o * 2 + 1] = max(maxx[o * 2 + 1],tag[o]);
        tag[o] = 0;
    }
}

void build(int o,int l,int r)
{
    tag[o] = maxx[o] = 0;
    if (l == r)
    {
        maxx[o] = a[l] * a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(o * 2,l,mid);
    build(o * 2 + 1,mid + 1,r);
    pushup(o);
}

ll query(int o,int l,int r,int poss)
{
    if (l == r)
        return maxx[o];
    pushdown(o);
    int mid = (l + r) >> 1;
    if (poss <= mid)
        return query(o * 2,l,mid,poss);
    else
        return query(o * 2 + 1,mid + 1,r,poss);
}

void update(int o,int l,int r,int x,int y,ll v)
{
    if (x <= l && r <= y)
    {
        tag[o] = max(v,tag[o]);
        maxx[o] = max(v,maxx[o]);
        return;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (x <= mid)
        update(o * 2,l,mid,x,y,v);
    if (y > mid)
        update(o * 2 + 1,mid + 1,r,x,y,v);
    pushup(o);
}

int main()
{
    while (~scanf("%d",&n))
    {
        init();
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld",&a[i]);
            nextmax[i] = nextmin[i] = n + 1;
        }
        for (int i = 1; i <= n; i++)
        {
            while (head > 0 && sta[head] > a[i])
            {
                nextmin[pos[head]] = i;
                head--;
            }
            sta[++head] = a[i];
            pos[head] = i;
        }
        head = 0;
        memset(pos,0,sizeof(pos));
        memset(sta,0,sizeof(sta));
        for (int i = 1; i <= n; i++)
        {
            while (head > 0 && sta[head] < a[i])
            {
                nextmax[pos[head]] = i;
                head--;
            }
            sta[++head] = a[i];
            pos[head] = i;
        }
        for (int i = 1; i <= n; i++)
        {
            cur1 = cur2 = i;
            ll maxxx = a[i],minnn = a[i],last = i;
            //update(1,1,n,1,1,maxxx * minnn);
            while (cur1 <= n && cur2 <= n)
            {
                if (nextmin[cur1] < nextmax[cur2])
                {
                    last = cur1;
                    cur1 = nextmin[cur1];
                    update(1,1,n,last - i + 1,cur1 - 1 - i + 1,minnn * maxxx);
                    minnn = a[cur1];
                }
                else
                {
                    last = cur2;
                    cur2 = nextmax[cur2];
                    update(1,1,n,last - i + 1,cur2 - 1 - i + 1,minnn * maxxx);
                    maxxx = a[cur2];
                }
            }
        }
        for (int i = 1; i <= n; i++)
            printf("%lld
",query(1,1,n,i));
    }

    return 0;
}

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
int n;
ll a[100010],ans[100010],temp[100010];

void solve(int l,int r)
{
    if (l == r)
        ans[1] = max(ans[1],a[l] * a[l]);
    if (l >= r)
        return;
    int id = l;
    for (int i = l; i <= r; i++)
        if (a[i] < a[id])
            id = i;
    solve(l,id - 1);
    solve(id + 1,r);
    for (int i = 1; i <= r - l + 1; i++)
        temp[i] = 0;
    for (int i = l; i <= id; i++)
        temp[id - i + 1] = max(temp[id - i + 1],a[i] * a[id]);
    for (int i = id + 1; i <= r; i++)
        temp[i - id + 1] = max(temp[i - id + 1],a[i] * a[id]);
    ll res = 0;
    for (int i = 1; i <= r - l + 1; i++)
    {
        res = max(res,temp[i]);
        ans[i] = max(ans[i],res);
    }
}

int main()
{
    while (scanf("%d",&n) != EOF)
    {
        memset(ans,0,sizeof(ans));
        for (int i = 1; i <= n; i++)
            scanf("%lld",&a[i]);
        solve(1,n);
        for (int i = 1; i <= n; i++)
            printf("%lld
",ans[i]);
    }

    return 0;
}