【NOIP2016提高A组五校联考4】ksum

题目

分析

发现，当子段[l,r]被取了出来，那么[l-1,r]、[l,r+1]一定也被取了出来。

那么，首先将[1,n]放入大顶堆，每次将堆顶的子段[l,r]取出来，因为它是堆顶，所以一定是最大的子段，输出它，并将[l+1,r]和[l,r-1]放进堆中。

一共就只用做k次就可以了。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=100005;

using namespace std;

long long n,m,a[N],sum[N],t[N*3][3],tot=1;

int swap(int x,int y,int z)

{

	t[x][z]=t[x][z]^t[y][z];

	t[y][z]=t[x][z]^t[y][z];

	t[x][z]=t[x][z]^t[y][z];

}

int up(int x)

{

	while(t[x][2]>t[x/2][2] && x!=1)

	{

		for(int i=0;i<=2;i++)

			swap(x,x/2,i);

		x/=2;

	}

}

int down(int x)

{

	int s=x*2,s1=x*2+1;

	while((t[x][2]<t[s][2] || t[x][2]<t[s1][2]) && s<=tot)

	{

		if(t[x][2]>t[s][2] && s1>tot) break;

		if(t[s][2]>t[s1][2])

		{

			for(int i=0;i<=2;i++)

				swap(x,s,i);

			x=s;

		}

		else

		if(s1<=tot)

		{

			for(int i=0;i<=2;i++)

				swap(x,s1,i);

			x=s1;

		}

		s=x*2,s1=x*2+1;

	}

}

int insert(int x,int y)

{

	t[++tot][0]=y;

	t[tot][1]=x;

	t[tot][2]=sum[x]-sum[y-1];

	up(tot);

}

int cut()

{

	t[1][0]=t[tot][0];

	t[1][1]=t[tot][1];

	t[1][2]=t[tot--][2];

	t[tot+1][0]=t[tot+1][1]=t[tot+1][2]=0;

	down(1);

}

int main()

{

	scanf("%lld%lld",&n,&m);

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

	{

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

		sum[i]=sum[i-1]+a[i];

	}

	tot=1;

	t[tot][0]=1;

	t[tot][1]=n;

	t[tot][2]=sum[n]-sum[0];

	while(m--)

	{

		printf("%lld ",t[1][2]);

		int x=t[1][1],y=t[1][0]+1,x1=t[1][1]-1,y1=t[1][0];

		cut();

		if(x==n) if(x>=y) if(y<=n) insert(x,y);

		if(x1>=y1) if(x1>=1) insert(x1,y1);

	}

}