[Bzoj1112][POI2008]砖块Klo（splay）

1112: [POI2008]砖块Klo

---

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2353  Solved: 831
[Submit][Status][Discuss]

Description

---

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

Input

---

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

Output

---

最小的动作次数

Sample Input

---

Sample Output

---

HINT

---

原题还要求输出结束状态时,每柱砖的高度.本题略去.

分析：

---

splay求中位数。

 

AC代码：

---

# include <iostream>

# include <cstdio>

# include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + ;

LL s[N],ret = 1e18;int n,K,root,cnt;

struct node{

   int ch[];

   int fa;

   int sz;LL val,sum;

   node(){}

   node(LL val):fa(),sz(),val(val),sum(sum){ch[] = ch[] = ;}

}a[N];

void push(int x)

{

    a[x].sz = a[a[x].ch[]].sz + a[a[x].ch[]].sz + ;

    a[x].sum = a[a[x].ch[]].sum + a[a[x].ch[]].sum + a[x].val;

}

void rotate(int now,int d)

{

    int pre = a[now].fa,g = a[pre].fa,nex = a[now].ch[d];

    a[pre].ch[d ^ ] = nex;

    if(nex)a[nex].fa = pre;

    a[now].fa = g;

    if(g)a[g].ch[a[g].ch[] == pre] = now;

    a[pre].fa = now;a[now].ch[d] = pre;

    push(pre);push(now);

}

void splay(int now)

{

    int pre,g;

    while(a[now].fa)

    {

        pre = a[now].fa,g = a[pre].fa;

        if(g && !((a[pre].ch[] == now) ^ (a[g].ch[] == pre)))rotate(pre,a[pre].ch[] == now);

        rotate(now,a[pre].ch[] == now);

    }

    root = now;

}

void insert(LL val)

{

    if(!root){a[++cnt] = node(val);root = cnt;return;}

    int now = root,pre;

    while(now)

    {

        pre = now;

        now = a[now].ch[val > a[now].val];

    }

    a[++cnt] = node(val);a[cnt].fa = pre;

    a[pre].ch[val > a[pre].val] = cnt;

    splay(cnt);

}

void erase(int now)

{

    splay(now);

    if(!a[now].ch[] || !a[now].ch[]){root = a[now].ch[] + a[now].ch[];}

    else

    {

        int p = a[now].ch[];

        while(a[p].ch[])p = a[p].ch[];

        a[p].ch[] = a[now].ch[];

        a[a[now].ch[]].fa = p;

        root = a[now].ch[];a[root].fa = ;

        splay(a[now].ch[]);

    }

    a[root].fa = ;

}

int find(int k)

{

    int now = root;

    while(k > )

    {

        if(a[a[now].ch[]].sz < k){k -= a[a[now].ch[]].sz;k--;if(k > )now = a[now].ch[];}

        else now = a[now].ch[];

    }

    return now;

}

int main()

{

  scanf("%d %d",&n,&K);

  for(int i = ;i <= n;i++)scanf("%lld",&s[i]);

  for(int i = ;i < K;i++)insert(s[i]);

  for(int i = K;i <= n;i++)

  {

      if(i - K)erase(i - K);

      insert(s[i]);

      int now = find((K + ) >> );

      splay(now);

      LL s1 = a[a[now].ch[]].sz,s2 = a[a[now].ch[]].sz;

      LL pre = a[a[now].ch[]].sum,bef = a[a[now].ch[]].sum;

      if(s1 * a[now].val - pre + bef - s2 * a[now].val < ret)ret = s1 * a[now].val - pre + bef - s2 * a[now].val;

  }

  printf("%lld\n",ret);

}