[JZOJ 4815]【NOIP2016提高A组五校联考4】ksum

Sample Input
样例输入1：
3 4
1 3 4
样例输入2：
3 3
10 2 7
Sample Output
样例输出1：
8 7 4 4
样例输出2：
19 12 10

The Solution

我们可以发现，如果当前最大的是[l,r]字段，那么易得[l,r+1]子段
和[l-1,r]子段一定之前就已经取出。
而且最大的子段一定是[1,n],
我们先把[1,n]放入堆里，
我们把子段加进一个堆，
假设当前堆顶是[a,b],这次之后，
[a+1,b]和[a,b-1]才有可能成为下次取出的对象，
那么我就将[a+1,b]和[a,b-1]加进堆，这样重复 k 次即可。时
间复杂度O(n log)。

Code

#include <cstdio>
#include <iostream>
#define fo(i,a,b) for (int i=a;i<=b;i++)
#define N 200005 

using namespace std;

typedef long long ll;

int num=0,n,k;
ll Pre[N];

struct node
{
    int l,r;ll sum;
}a[N];

void Up(int x)
{ 
    for (;x>1 && a[x].sum > a[x >> 1].sum;x >>= 1) swap(a[x],a[x >> 1]);
}

void Down(int x)
{
while (2*x <= num && a[x].sum <= a[2*x].sum || (2*x+1 <= num) && a[x].sum <= a[2*x+1].sum)
    {
        int y = 2 * x;
if (y+1 <= num && a[y+1].sum > a[y].sum) y++;
        swap(a[x],a[y]);
        x=y;
    }
}
void Insert(int l,int r,ll s)
{
a[++ num].l = l;
a[num].r = r;
a[num].sum = s;
    Up(num);
}

void Delete(int x)
{
if (a[num].sum < a[x].sum) 
    {
a[x].l = a[num].l;
a[x].r = a[num].r;
a[x].sum = a[num --].sum;
        Down(x);
    }
else 
    {
a[x].l = a[num].l;
a[x].r = a[num].r;
a[x].sum = a[num --].sum;
        Up(x);
    }
}

int main()
{
    freopen("ksum.in","r",stdin);
    freopen("ksum.out","w",stdout); 
    scanf("%d%d",&n,&k);
    int sum,x;
    fo(i,1,n) scanf("%d",&x),Pre[i]+=Pre[i-1]+(ll)x;
    Insert(1,n,Pre[n]);
while (k--)
    {
        printf("%lld ",a[1].sum);
if (a[1].l+1 <= a[1].r && a[1].r == n) Insert(a[1].l+1,a[1].r,Pre[a[1].r]-Pre[a[1].l]);
if (a[1].l <= a[1].r-1) Insert(a[1].l,a[1].r-1,Pre[a[1].r-1]-Pre[a[1].l-1]);
        Delete(1);
    }   
return 0;
}

这里有另一种库里的堆调用

#include<cstdio>
#include<queue>
using namespace std;
struct data{int l,r;}p;
long long pre[100001];
inline int read()
{
int data=0; char ch=0;
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
return data;
}
inline bool operator<(data a,data b)
{
return pre[a.r]-pre[a.l-1]<pre[b.r]-pre[b.l-1];
}
priority_queue <data> que;
int main()
{
    freopen("ksum.in","r",stdin);
    freopen("ksum.out","w",stdout);
int n=p.r=read(),k=read();
for(int i=p.l=1;i<=n;i++) pre[i]=pre[i-1]+read();
    que.push(p);
while(k--)
    {
        p=que.top();
        que.pop();
printf("%lld ",pre[p.r]-pre[p.l-1]);
if(p.r==n)
        {
            p.l++;
            que.push(p);
            p.l--;
        }
        p.r--;
        que.push(p);
    }
return 0;
}