【BZOJ1112】[POI2008]砖块Klo

2015.08.12 18:59 Wed | 37次阅读 | 旧日oi | 固定链接 | 源码

Description

N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.

Input

第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000

题解

裸的动态找中位数问题嘛,直接平衡树上呗。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
#define N 100005
int n,K,h[N],size,root;
ll ans=0x7fffffffffffffffll,sum;
struct treap{
    int l,r,size,rnd,w;
    ll sum,v;
}tpt[N];
void update(int k)
{
    tpt[k].size=tpt[tpt[k].l].size+tpt[tpt[k].r].size+tpt[k].w;
    tpt[k].sum=tpt[tpt[k].l].sum+tpt[tpt[k].r].sum+tpt[k].v*tpt[k].w;
}
void rturn(int &k)
{
    int t=tpt[k].l;tpt[k].l=tpt[t].r;tpt[t].r=k;
    tpt[t].size=tpt[k].size;update(k);update(t);k=t;
}
void lturn(int &k)
{
    int t=tpt[k].r;tpt[k].r=tpt[t].l;tpt[t].l=k;
    tpt[t].size=tpt[k].size;update(k);update(t);k=t;
}
void insert(int &k,int x)
{
    if(k==0)
    {
        size++;k=size;
        tpt[k].size=tpt[k].w=1;
        tpt[k].v=tpt[k].sum=x;
        tpt[k].rnd=rand();
        return;
    }
    tpt[k].size++;
    if(tpt[k].v==x) tpt[k].w++;
    else if(tpt[k].v<x){
        insert(tpt[k].r,x);
        if(tpt[tpt[k].r].rnd<tpt[k].rnd) lturn(k);
    }
    else{
        insert(tpt[k].l,x);
        if(tpt[tpt[k].l].rnd<tpt[k].rnd) rturn(k);
    }
    update(k);
}
void del(int &k,int x){
    if(k==0) return;
    if(tpt[k].v==x){
        if(tpt[k].w>1){
            tpt[k].w--;tpt[k].size--;
            tpt[k].sum-=tpt[k].v;
            return;
        }
        if(tpt[k].l*tpt[k].r==0) k=tpt[k].l+tpt[k].r;
        else if(tpt[tpt[k].l].rnd<tpt[tpt[k].r].rnd)
            rturn(k),del(k,x);
        else lturn(k),del(k,x);
    }
    else if(tpt[k].v<x) tpt[k].size--,del(tpt[k].r,x);
    else tpt[k].size--,del(tpt[k].l,x);
    update(k);
}
ll v;
ll find(int x,int k)
{
    ll sum=0;
    while(x)
    {
        if(tpt[tpt[x].l].size>k) x=tpt[x].l;
        else if(tpt[tpt[x].l].size+tpt[x].w>k)
        {
            sum+=tpt[tpt[x].l].sum+(k-tpt[tpt[x].l].size)*tpt[x].v;
            v=tpt[x].v;
            return sum;
        }
        else
        {
            sum+=tpt[tpt[x].l].sum+tpt[x].v*tpt[x].w;
            k-=tpt[tpt[x].l].size+tpt[x].w;
            x=tpt[x].r;
        }
    }
    return sum;
}
int f[N],flag;
int main()
{
    //freopen("klo11c.in", "r", stdin);
    //freopen("klo.out", "w", stdout);
    cin>>n>>K;
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    insert(root,h[0]);
    for(int i=1;i<=n;i++)
    {
        insert(root,h[i]);sum+=h[i];
        if(i>=K)
        {
            del(root,h[i-K]),sum-=h[i-K];
            ll t=find(root,K/2);
            f[i]=v;
            if(ans>sum-2*t-(K&1)*v)
            {
                ans=sum-2*t-(K&1)*v;
                flag=i;
            }
        }
    }
    cout<<ans<<endl;
}```