1693: ksum

Time Limit: 1000 ms
Memory Limit: 524288 KBytes
Judge: Standard Judge
Solved: 18
Submit: 41

Submit Status

Description

Peter喜欢玩数组。NOIP这天，他从Jason手里得到了大小为n的一个正整数数组。

Peter求出了这个数组的所有子段和，并将这n(n+1)/2个数降序排序，他想知道前k个数是什么。

Input Format

输入文件名为 ksum.in。

输入数据的第一行包含两个整数 n 和 k。

接下来一行包含 n 个正整数，代表数组。

Output Format

输出文件名为 ksum.out。

输出 k 个数，代表降序之后的前 k 个数，用空格隔开。

Sample Input

input1

3 4

1 3 4

input2

3 3

10 2 7

Sample Output

output1

8 7 4 4

output2

19 12 10

Hint

测试点编号 n ≤ k ≤

1 100 5000

2 500 100000

3 1000 80000

4 1000 100000

5 10000 50000

6 20000 80000

7 50000 80000

8 100000 80000

9 100000 100000

10 100000 100000

对于所有数据，满足 ai≤10 9 k≤n(n+1)/2,n≤100000,k≤100000

明显的堆维护对于一段连续序列它的一系列次小值一定是这段序列的子集；

只要每次取出堆顶将堆顶序列分别由（l+1,r）&&(l,r-1)的子序列塞入堆中

进行堆维护即可注意过程可能出现重复顶点用哈希表维护即可；

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<map>

#include<vector>

#define maxn 100010

using namespace std;

struct st

{

    int l,r;

    long long sum;

}mu[*maxn];

typedef pair<int,int> pa;

map <pa,bool>q1;

int n,m,k,l,n1,i;

int a[maxn];

void down(int x)

{

    int fa=x,son;

    while(fa*<=n1)

    {

        son=fa*;

        if(mu[son+].sum>mu[son].sum&&son+<=n1)son++;

        if(mu[fa].sum>mu[son].sum)break;

        swap(mu[fa],mu[son]);

        fa=son;

    }

}

void up(int x)

{

    int fa,son=x;

    while(son/)

    {

        fa=son/;

        if(mu[fa].sum>mu[son].sum)break;

        swap(mu[fa],mu[son]);

        son=fa;

    }

}

void push (st x)

{

    n1++; q1[pa(x.l,x.r)]=;

    mu[n1]=x;

    up(n1);

}

int main()

{

//    freopen("ksum.in","r",stdin);

//    freopen("ksum.out","w",stdout);

    scanf("%d%d",&n,&k);

    for(i=;i<=n;++i)

    {

        scanf("%d",&a[i]);

        mu[].sum+=a[i];

    }

    n1=;mu[].l=;mu[].r=n;q1[pa(mu[].l,mu[].r)]=;

    for(i=;i<=k;++i)

    {

        printf("%lld ",mu[].sum);

        if(mu[].l<mu[].r)

        {

            st q;

            q=mu[];

            q.sum-=a[q.l];

            q.l++;

            if(!q1[pa(q.l,q.r)])

            push(q);

            q=mu[];

            q.sum-=a[q.r];

            q.r--;

            if(!q1[pa(q.l,q.r)])

            push(q);

        }

        mu[]=mu[n1--];

        down();

    }

}

ksum