题目

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

分析

发现,当子段[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);
}
}
05-11 19:40