《算法竞赛进阶指南》0x17二叉堆 链表+红黑树实现高效插入、删除、取最小值

题目链接：https://www.acwing.com/problem/content/149/

题目中给出一些点在x轴上的位置，问选出k对位置的情况下，他们的两两距离之和的最小值是多少？容易直到，选中的位置一定是相邻的而且没有交集，我们对原始序列求差分之后问题

就变成了在这个差分序列中寻找k个不相邻的数，使得和最小。

当选中了其中的k个两两间隔为1的位置之后，如果下一次从剩下的区间里面选出一个最小的区间跟这k个点相邻就破坏了性质，这k个点一定会被周围的k+1个点取代，从数学上

可以证明：取代之后的情况了，值增加了的d[left]+d[right]-d[podition]（一个点的性质被破坏）,也可以证明k个点被破坏之后的更新方式是一样的，就相当于三个结点变成了一个结点一样

原子性证明引用：

所以我们只需要维护最小值以及删除最小值左右结点以及添加结点的操作，这些操作在红黑树中都能够高效实现。

代码：

#include<iostream>
#include<set>
using namespace std;
#define maxn 100010
typedef long long ll;
int l[maxn],r[maxn];//双向链表存储位置
ll d[maxn];
int n,k;
set< pair<ll,int> > s;//红黑树存储最小值以及最小值对应的下标,便于删除以及查询最小值
void delete_node(int x){//双向链表中删除一个结点 
    l[r[x]]=l[x];
    r[l[x]]=r[x]; 
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        scanf("%lld",&d[i]);
    }
    for(int i=n-1;i>0;i--)d[i]-=d[i-1];
    d[0]=d[n]=1e15;//添加哨兵结点 ,防止选择的时候越界 
    for(int i=0;i<=n;i++)
    {
        l[i]=i-1;
        r[i]=i+1;
        if(i>=1 && i<n)s.insert(make_pair(d[i],i));//n-1个差分存入红黑树 
    }
    ll res=0;
    while(k--){
        auto it=s.begin();//取出最小的值 
        ll v=it->first;
        int pos=it->second;
        s.erase(it);//删除结点并且删除结点的左右结点 
        int left=l[pos],right=r[pos];
        s.erase(make_pair(d[left],left));
        s.erase(make_pair(d[right],right));
        delete_node(left),delete_node(right);
        d[pos]=d[left]+d[right]-d[pos];
        s.insert(make_pair(d[pos],pos));
        res+=v;
    }
    cout<<res<<endl;
    return 0; 
}