记录编号	466395	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.168 s
提交时间	2017-10-28 21:26:49	内存使用	3.56 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0),f(1);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
int n,m,a[200005],heap[200005],top,ans;
inline void push(int x){
	heap[++top]=x;int now(top);//cout<<top<<endl;
	while(1){//cout<<now<<endl;
		if(now<=1)break;
		if(a[heap[now>>1]]>=a[heap[now]])break;
		else swap(heap[now>>1],heap[now]),now>>=1;
	}
}
inline int get_top(){
	int ret(heap[1]);swap(heap[1],heap[top--]);int now(1),son;//cout<<top<<endl;
	while(1){//cout<<now<<endl;
		if((now<<1)>top)break;
		if((now<<1|1)<=top&&a[heap[now<<1|1]]>=a[heap[now<<1]])son=now<<1|1;
		else son=now<<1;
		if(a[heap[son]]<=a[heap[now]])break;
		else swap(heap[now],heap[son]),now=son;
	}
	return ret;
}
int pre[200005],nxt[200005];
bool vis[200005];
int main(){
	freopen("nt2011_tree.in","r",stdin);freopen("nt2011_tree.out","w",stdout);
	n=read(),m=read();if(m>(n>>1)){puts("Error!");return 0;}
	for(int i=1;i<=n;++i)a[i]=read(),push(i),pre[i]=i-1,nxt[i]=i+1;pre[1]=n;nxt[n]=1;
	while(m--){
		int top(get_top());while(vis[top])top=get_top();
		int pr(pre[top]),nx(nxt[top]),ppr(pre[pr]),nnx(nxt[nx]);
		ans+=a[top];a[top]=a[pr]+a[nx]-a[top];
		nxt[ppr]=top;pre[nnx]=top;pre[top]=ppr;nxt[top]=nnx;
		push(top);vis[pr]=vis[nx]=1;
	}
	printf("%d",ans);
}