记录编号	145098	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.250 s
提交时间	2015-01-02 15:22:44	内存使用	13.67 MiB

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define size 200001
int heap[size],heapsize=1,point[size],a[size],l[size],r[size];
inline void down(int x){
	int now=x,next=x<<1;
	//cout<<"D:"<<heap[x]<<endl;
	while(next<heapsize){
		if(next+1<heapsize&&a[heap[next+1]]>a[heap[next]])++next;
		if(a[heap[now]]>a[heap[next]]){/*
			for(int i=1;i<heapsize;++i)
				printf("%d(%d) ",heap[i],a[heap[i]]);
			cout<<endl;*/
			return;
		}
		//cout<<"(D)"<<heap[now]<<":"<<now<<"->"<<next<<endl;
		swap(heap[now],heap[next]);
		swap(point[heap[now]],point[heap[next]]);
		now=next,next<<=1;
	}
}
inline void up(int x){
	int now=x,next=x>>1;
	//cout<<"U:"<<heap[x]<<endl;
	while(next){
		if(a[heap[next]]>a[heap[now]]){/*
			for(int i=1;i<heapsize;++i)
				printf("%d(%d) ",heap[i],a[heap[i]]);
			cout<<endl;*/
			return;
		}
		//cout<<"(U)"<<heap[now]<<":"<<now<<"->"<<next<<endl;
		swap(heap[now],heap[next]);
		swap(point[heap[next]],point[heap[now]]);
		now=next,next>>=1;
	}
}
char * ptr=(char *)malloc(10000000);
inline void in(int &x){
	bool flag=0;
	while(*ptr<'0'||*ptr>'9')
		if(*ptr++=='-')
			flag=1;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
	if(flag)x=-x;
}
int main(){
	freopen("nt2011_tree.in","r",stdin);
	freopen("nt2011_tree.out","w",stdout);
	int N,M,i,ans=0;
	fread(ptr,1,10000000,stdin);
	in(N),in(M);
	if(N<M<<1){
		printf("Error!");
		return 0;
	}
	for(i=0;i<N;++i)in(a[i]);
	for(i=N-2;i;--i)
		l[i]=i-1,r[i]=i+1;
	l[0]=N-1,r[0]=1,l[N-1]=N-2,r[N-1]=0;
	for(i=0;i<N;++i){
		point[i]=heapsize;
		heap[heapsize]=i;
		up(heapsize++);
		down(point[i]);
	}/*
	printf("\n-----------0----------\n");
	for(int i=1;i<heapsize;++i)
		printf("%d(%d) ",heap[i],a[heap[i]]);*/
	while(M--){
		ans+=a[heap[1]];
		//cout<<heap[1]<<":"<<l[heap[1]]<<" "<<r[heap[1]]<<endl;
		
		heap[point[l[heap[1]]]]=heap[--heapsize];
		point[heap[heapsize]]=point[l[heap[1]]];
		up(point[heap[heapsize]]);
		down(point[heap[heapsize]]);
		
		heap[point[r[heap[1]]]]=heap[--heapsize];
		point[heap[heapsize]]=point[r[heap[1]]];
		up(point[heap[heapsize]]);
		down(point[heap[heapsize]]);
		
		a[heap[1]]=a[l[heap[1]]]+a[r[heap[1]]]-a[heap[1]];
		l[heap[1]]=l[l[heap[1]]];
		r[heap[1]]=r[r[heap[1]]];
		l[r[heap[1]]]=heap[1];
		r[l[heap[1]]]=heap[1];
		down(1);
		
		/*printf("-----------%d----------\n",M);
		for(int i=1;i<heapsize;++i)
			printf("%d(%d) ",heap[i],a[heap[i]]);
		cout<<endl;*/
	}
	printf("%d",ans);
}