BZOJ4071: [Apio2015]巴鄰旁之橋

首先對於家和公司在同一側的預處理掉，這樣就只剩家和公司不在同一側的情況了。
if(K==1)ans=∑abs(x-pos)+abs(y-pos);注意到與x，y是否在兩側無關，所以用經典的中位數處理思想sort一遍取中位數貪心即可。
else{
一個人要走的距離是abs(x-pos)+abs(y-pos)，讓它最短話句話說就是讓中點距pos盡可能近，於是我們將所有區間按中點排序，枚舉從哪個重中點分成兩塊，左面走左面的橋右面走右面的橋，平衡樹或者權值線段樹動態維護中位數即可。
}
好久不寫splay，練習了一發…>_<…

#include
#include
#include
#include
#define ll long long
//by:MirrorGray
using namespace std;
const int N=211111,inf=0x3f3f3f3f;
struct node{
    int x,y;
    node(int a=0,int b=0){
        x=a;y=b;
    }
    bool operator <(const node&b)const{
        return x+y=d)return nxt(sp[tr].l,d,tr);
        else return nxt(sp[tr].r,d,ret);
    }
    int kth(int tr,int k){
        if(sp[sp[tr].l].size>=k)return kth(sp[tr].l,k);
        if(sp[sp[tr].l].size+sp[tr].gs>=k)return tr;
        return kth(sp[tr].r,k-(sp[sp[tr].l].size+sp[tr].gs));
    }
    void insert(int d){
        int t1=pre(root,d,-1);splay(t1,0);
        int t2=nxt(root,d,-1);splay(t2,t1);
        if(sp[t2].d==d){
            sp[t2].gs++;
            up(t2);up(t1);
            return ;
        }
        sp[t2].l=++cnt;
        sp[cnt].d=d;sp[cnt].fa=t2;sp[cnt].gs=1;
        up(cnt);up(t2);up(t1);
    }
    void del(int d){
        int t1=pre(root,d,-1);splay(t1,0);
        int t2=nxt(root,d+1,-1);splay(t2,t1);
        int tr=sp[t2].l;
        if(sp[tr].gs>1){
            sp[tr].gs--;
            up(tr);up(t2);up(t1);
            return ;
        }
        sp[t2].l=0;
        up(t2);up(t1);
    }
    ll Q(){
        ll ret=0;
        int tr=kth(root,sp[root].size>>1);
        splay(tr,0);int l=sp[tr].l,r=sp[tr].r;
//      cout<<"size : "<