BZOJ 1112 [POI2008]砖石Klo Treap

题意:链接

方法: Treap

解析:

我们线性扫区间，然后每个区间的中位数肯定是这个区间的选取的高度。

搞出这个高度后我们要将这个区间内的所有的数与选取的高度作差取绝对值求和。

所以转化成，我们需要一种数据结构支持删点，加点，找排名为rnk的数，询问部分求和。

所以上个Treap就好了。

至于求和，记个sum，比中位数小的用中位数乘个数减求和，比中位数大的用求和减中位数乘个数。

说了这么多其实就是个水题- -!

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define N 100010
using namespace std;
typedef long long ll;
int n,k;
ll h[N];
int tot;
int size,root;
struct node
{
    int l,r,rnd;
    ll siz,w,v,sum;
}tr[N];
void pushup(int &rt)
{
    tr[rt].siz=1+tr[tr[rt].l].siz+tr[tr[rt].r].siz;
    tr[rt].sum=tr[rt].v+tr[tr[rt].l].sum+tr[tr[rt].r].sum;
}
void lturn(int &rt)
{
    int t=tr[rt].r;
    tr[rt].r=tr[t].l;
    tr[t].l=rt;
    tr[t].siz=tr[rt].siz;
    pushup(rt);
    rt=t;
}
void rturn(int &rt)
{
    int t=tr[rt].l;
    tr[rt].l=tr[t].r;
    tr[t].r=rt;
    tr[t].siz=tr[rt].siz;
    pushup(rt);
    rt=t;
}
void insert(int &rt,ll v)
{
    if(!rt)
    {
        rt=++size;
        tr[rt].siz=1;
        tr[rt].v=v,tr[rt].sum=v;
        tr[rt].rnd=rand();
        return;
    }
    tr[rt].siz++;
    if(v<=tr[rt].v)
    {
        insert(tr[rt].l,v);
        if(tr[tr[rt].l].rnd<tr[rt].rnd)rturn(rt);
    }else
    {
        insert(tr[rt].r,v);
        if(tr[tr[rt].r].rnd<tr[rt].rnd)lturn(rt);
    }
    pushup(rt);
}
void del(int &rt,ll v)
{
    if(!rt)return;
    tr[rt].siz--;
    if(tr[rt].v==v)
    {
        if(tr[rt].l*tr[rt].r==0){rt=tr[rt].l+tr[rt].r;return;}
        if(tr[tr[rt].l].rnd<tr[tr[rt].r].rnd)rturn(rt),del(tr[rt].r,v);
        else lturn(rt),del(tr[rt].l,v);
    }else if(v<tr[rt].v)del(tr[rt].l,v);
    else del(tr[rt].r,v);
    pushup(rt);
}
ll q_val(int rt,int rnk)
{
    if(tr[tr[rt].l].siz+1==rnk)return tr[rt].v;
    else if(rnk<tr[tr[rt].l].siz+1)return q_val(tr[rt].l,rnk);
    else return q_val(tr[rt].r,rnk-tr[tr[rt].l].siz-1);
}
ll q_sum_pre(int rt,int rnk)
{
    if(!rnk)return 0;
    if(tr[tr[rt].l].siz+1==rnk)return tr[tr[rt].l].sum+tr[rt].v;
    else if(rnk<tr[tr[rt].l].siz+1)return q_sum_pre(tr[rt].l,rnk);
    else return tr[tr[rt].l].sum+tr[rt].v+q_sum_pre(tr[rt].r,rnk-tr[tr[rt].l].siz-1);
}
ll q_sum_sub(int rt,int rnk)
{
    if(!rnk)return 0;
    if(tr[tr[rt].l].siz+1==rnk)return tr[tr[rt].r].sum+tr[rt].v;
    else if(rnk<tr[tr[rt].l].siz+1)return tr[tr[rt].r].sum+tr[rt].v+q_sum_sub(tr[rt].l,rnk);
    else return q_sum_sub(tr[rt].r,rnk-tr[tr[rt].l].siz-1);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
    ll ans=0x3f3f3f3f3f3f3f3fll;
    for(int i=1;i<=n;i++)
    {
        if(i<k)insert(root,h[i]);
        else if(i==k)
        {
            insert(root,h[i]);
            ll mid=q_val(root,(k+1)>>1);
            ll sum1=q_sum_pre(root,(k+1)>>1);
            ll sum2=q_sum_sub(root,((k+1)>>1)+1);
            ans=min(ans,mid*((k+1)>>1)-sum1+sum2-mid*(k-((k+1)>>1)));
        }else
        {
            del(root,h[i-k]);
            insert(root,h[i]);
            ll mid=q_val(root,(k+1)>>1);
            ll sum1=q_sum_pre(root,(k+1)>>1);
            ll sum2=q_sum_sub(root,((k+1)>>1)+1);
            ans=min(ans,mid*((k+1)>>1)-sum1+sum2-mid*(k-((k+1)>>1)));
        }
    }
    printf("%lld\n",ans);
}