记录编号	275658	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.256 s
提交时间	2016-07-02 19:53:03	内存使用	2.79 MiB

/*
很神的题。。。。。。
我太弱，没想出来。。。。。。

题解：
首先考虑如果没有“相邻位置不能都种”这一限制会怎么样。
这时就是一个裸的贪心――按照A[i]从大到小排序，然后取前M个。

那么加上限制以后会发生什么呢？
[国家集训队2011]种树 <wbr>解题报告
假设A[3]最大，那我们就试图去选A[3]。选中之后首先要去掉3，
并且，A[2]和A[4]也都不能选了，所以将它们删掉――

但是慢着！这可能会导致问题。假设A[3]=20,A[2]=A[4]=19，
那么同时选A[2],A[4]可能比选A[3]要优！在最后的方案中可能是A[2]+A[4]而非A[3]。
这种情况要怎么解决呢？

可以发现一点：由于A[3]最大，所以在最后的方案中，不可能只选A[2],A[4]中的一个。
原因很简单：假设在最优方案中选了A[2]但未选A[4]，
那可以简单地把A[2]换成A[3]，由于未选A[4]，
所以这样不会产生任何矛盾，并且把A[2]换成A[3]后，总的美观度不会下降。

因此，我们先去掉2,3,4，然后加入一个新的“物品”，
其权值为A[2]+A[4]-A[3]，代表同时选2,4，删去3.这样，
在选了3之后再选这个新物品，功效就相当于刚才所说的，把A[3]换成A[2]+A[4]。

这个新物品应该放在哪里呢？它的含义是“选2,4”，所以很容易想到，
应该把它放在1,5中间。
出于方便起见，不妨在删掉2,4后直接把A[3]改成A[2]+A[4]-A[3]，
显然这个位置是正确的。

如此就将N个物品，需要选M个的问题转化成了在N-1个物品中选的问题。
并且可以发现一个很好的性质：新的3所对应的仍然是“选中物品数+1”！
（把选3换成了选2,4，即多选了一个物品）

也就是说，完全可以把新的3看做一个和1，5毫无区别的物品，
现在我们只需要在1,3,5三个物品中选择M-1个！如此下去，直到选择M次，
就可以得到答案。

因此描述一下算法：以A[i]为关键字建大根堆，用一个链表存放当前物品。
最初链表中元素是1~N，i的后继是i+1，前驱是i-1（当然，1的前驱是N，N的后继是1）。
执行M次操作，每一次操作都将堆顶元素k取出，ans+=A[k]。
然后在链表中删除k的前驱pre和后继nxt，令A[k]=A[pre]+A[nxt]-A[k]，并更新堆。

这个算法运行的很好，但你可能感觉有点虚――为什么每次选A值最大的就正确呢？
可以发现，在上面的讨论中“选3”时，我们实际上做的是声明如下事实：
在最终答案中要么选了3，要么同时选了2,4.换句话说，要么选了3，
要么在此基础上选了A[2]+A[4]-A[3]。

所以我们实际上是重写了这个问题，将其变成“N-2个物品中选M-1”
个的形式，如此一直化归，直到最后变成“N-2(M-1)个物品中选1个”，
这时答案就是显然的。 
*/
#include<stdio.h>
#include<queue>
#include<iostream>
#define pa pair<int,int>
using namespace std;
int ans,n,m,cnt,a[200010],pre[200010],nx[200010];
bool mk[200010];
priority_queue<pa>q;
void del(int x){
	mk[x]=1;
	int l=pre[x],r=nx[x];
	nx[x]=pre[x]=0;
	nx[l]=r,pre[r]=l;
}
void work(){
	while(mk[q.top().second])q.pop();
	int x=q.top().second;ans+=a[x];
	q.pop();
	a[x]=a[pre[x]]+a[nx[x]]-a[x];
	del(pre[x]),del(nx[x]);
	q.push(make_pair(a[x],x));
}
int main(){
	freopen("nt2011_tree.in","r",stdin);
	freopen("nt2011_tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	if(m>n>>1)return puts("Error!"),0;
	for(int i=1;i<=n;++i)pre[i]=i-1;pre[1]=n;
	for(int i=1;i<=n;++i)nx[i]=i+1;nx[n]=1;
	for(int i=1;i<=n;++i)q.push(make_pair(a[i],i));
	for(int i=1;i<=m;++i)work();
	printf("%d",ans);
}