1150: [CTSC2007]数据备份Backup

上面的插入、删除操作均需用堆维护。

想不通，把堆写错了。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<string>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define sqr(x) ((x)*(x))
#define G getchar()
#define LL long long
#define pii pair<int,int>
#define mkp make_pair
#define X first
#define Y second
#define N 100005  
#define inf 2139062143
int Hp[N],pos[N],sop[N],id;
int n,m,a[N],ans;
int zuo[N],you[N];
int read(){
	int x=0;char ch=G;
	while(ch<48||ch>57)ch=G;
	for(;ch>47&&ch<58;ch=G)x=x*10+ch-48;
	return x;
}
void Swap(int x,int y){
	swap(Hp[x],Hp[y]);
	swap(pos[sop[x]],pos[sop[y]]);
	swap(sop[x],sop[y]);
}
void ins(int x,int y){
	int i;sop[pos[x]=++id]=x;
	for(Hp[i=id]=y;i>1&&Hp[i]<Hp[i>>1];i>>=1)Swap(i,i>>1);
}
void del(int x){
/*	不知道错在哪里
	int i;
	for(Swap(i=x,id--);i<<1<=id&&Hp[i]>Hp[i<<1]||(i<<1|1)<=id&&Hp[i]>Hp[i<<1|1];)
		if((i<<1|1)>id||Hp[i<<1]<Hp[i<<1|1]){Swap(i,i<<1);i<<=1;}
		else{Swap(i,i<<1|1);i=i<<1|1;}
*/
	int i,y;Swap(x,id--);
	for(i=x;i>1&&Hp[i]<Hp[i>>1];i>>=1)Swap(i,i>>1);	while(1){
		y=x<<1;
		if(y>id)break;
		if(y<id&&Hp[y]>Hp[y|1])y|=1;
		if(Hp[y]>=Hp[x])break;
		Swap(x,y);x=y;
	}
}
int main(){
	int i,x,y,z;
	n=read();m=read();
	rep(i,1,n)a[you[zuo[i]=i-1]=i]=read();
	rep(i,1,n-1)ins(i,a[i+1]-a[i]);
	while(1){
		ans+=Hp[1];
		if(--m==0)break;
		x=sop[1];
		y=you[x];x=zuo[x];
		if(!x)del(1),del(pos[y]),zuo[you[0]=you[y]]=0;
		else if(y==n)del(1),del(pos[x]),you[zuo[n]=zuo[x]]=n;
		else{
			z=Hp[pos[x]]+Hp[pos[y]]-Hp[1];
			del(1);del(pos[x]);del(pos[y]);
			ins(x,z);
			zuo[you[x]=you[y]]=x;
		}
	}
	printf("%d\n",ans);
	return 0;
}