[HOJ] 229 - Backup

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100005
int s[N],L[N],R[N],Ls[N],Rs[N];
struct P{
    int l,r,p;
    friend bool operator < (P a,P b){
        return a.p>b.p;
    }
};
priority_queue<P> que;
int main(){
    int n,k,i,ans=0,x,y;
    int add;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d",&s[i]);
        L[i]=R[i]=i;
        Ls[i]=Rs[i]=0;
        if(i){
            L[i]=i-1;
            Ls[i]=s[i]-s[i-1];
            Rs[i-1]=s[i]-s[i-1];
            que.push((P){i-1,i,s[i]-s[i-1]});
        }
        if(i<n-1){
            R[i]=i+1;
        }
    }
    for(i=0;i<k;i++){

        while(R[que.top().l]!=que.top().r || L[que.top().r]!=que.top().l) que.pop();
        P edge=que.top();
        que.pop();
        ans+=edge.p;
        if(L[edge.l]!=edge.l && R[edge.r]!=edge.r){
            add=-edge.p;
            x=L[edge.l],y=edge.l;
            add+=Ls[edge.l];
            x=edge.r,y=R[edge.r];
            add+=Rs[edge.r];
            x=L[edge.l],y=R[edge.r];
            R[x]=y,L[y]=x;
            Ls[y]=Rs[x]=add;
            que.push((P){x,y,add});
            L[edge.l]=edge.l,R[edge.l]=edge.l;
            L[edge.r]=edge.r,R[edge.r]=edge.r;
        }
        else if(R[edge.r]!=edge.r){
            R[edge.l]=edge.l,L[R[edge.r]]=R[edge.r];
        }
        else if(L[edge.l]!=edge.l){
            L[edge.r]=edge.r,R[L[edge.l]]=L[edge.l];
        }
    }
    printf("%d\n",ans);
}