1112: [POI2008]砖块Klo

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 1245  Solved: 426

[][][]

Description

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

Input

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

Output

最小的动作次数

Sample Input

5 3

3

9

2

3

1

Sample Output

2

HINT

 

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

 

Source

 

题解：（呵呵呵我会说我逗到了用Splay做这题的地步么= =）

首先，看这道题，对于某个高度序列而言，很明显将所有高度都变为中位数代价最小

我觉得任何一个数竞党都该知道怎么样可以让下列式子值最小——

\( \sum_{i=1}^{N} \left | x-x_i \right | \)

其中，\( x_1 \leq x_2 \leq x_3 ... \leq x_N \)

显然，当N为奇数时， \( x=x_\frac{N+1}{2} \)

当N为偶数时， \( x_\frac{N}{2} \leq x \leq x_\frac{N+2}{2} \)

然后接下来讨论怎么实现——我们需要一棵平衡树，可以加入和删除值，可以查询指定排名的数位置（用来找中位数），还得可以快速求出当前序列中比中位数大的各个数之和，以及比它小的之和，这样子就很明显需要维护子树大小（用于排名），然后还得维护子树和，然后我为了偷懒就直接来了个splay，每次将中位数splay上来，然后两边的不就是我们要的两边和嘛，然后该怎么办怎么办，别的没了

 

1 /**************************************************************  2     Problem: 1112  3     User: HansBug  4     Language: Pascal  5     Result: Accepted  6     Time:6156 ms  7     Memory:27636 kb  8 ****************************************************************/  9   10 var 11    i,j,k,m,n,head:longint; 12    l,ans:int64; 13    lef,rig,b:array[0..1000000] of longint; 14    a,c:array[0..1000000] of int64; 15 procedure rt(var x:longint);inline; 16           var f,l:longint; 17           begin 18                if (x=0) or (lef[x]=0) then exit; 19                b[lef[x]]:=b[x];b[x]:=b[rig[lef[x]]]+b[rig[x]]+1; 20                c[lef[x]]:=c[x];c[x]:=c[rig[lef[x]]]+c[rig[x]]+a[x]; 21                f:=x;l:=lef[x]; 22                lef[f]:=rig[l]; 23                rig[l]:=f; 24                x:=l; 25           end; 26 procedure lt(var x:longint);inline; 27           var f,r:longint; 28           begin 29                if (x=0) or (rig[x]=0) then exit; 30                b[rig[x]]:=b[x];b[x]:=b[lef[rig[x]]]+b[lef[x]]+1; 31                c[rig[x]]:=c[x];c[x]:=c[lef[rig[x]]]+c[lef[x]]+a[x]; 32                f:=x;r:=rig[x]; 33                rig[f]:=lef[r]; 34                lef[r]:=f; 35                x:=r; 36           end; 37 procedure splay(var x:longint;y:longint);inline; 38           begin 39                if (x=0) or (y=0) then exit; 40                if y=(b[lef[x]]+1) then exit; 41                if y<(b[lef[x]]+1) then 42                   begin 43                        if (b[lef[lef[x]]]+1)=y then rt(x) else 44                           if y<(b[lef[lef[x]]]+1) then 45                              begin 46                                   splay(lef[lef[x]],y); 47                                   rt(x);rt(x); 48                              end 49                           else 50                               begin 51                                    splay(rig[lef[x]],y-b[lef[lef[x]]]-1); 52                                    lt(lef[x]);rt(x); 53                               end; 54                   end 55                else 56                    begin 57                         y:=y-1-b[lef[x]]; 58                         if y=(b[lef[rig[x]]]+1) then lt(x) else 59                            if y<(b[lef[rig[x]]]+1) then 60                               begin 61                                    splay(lef[rig[x]],y); 62                                    rt(rig[x]);lt(x); 63                               end 64                            else 65                                begin 66                                     splay(rig[rig[x]],y-1-b[lef[rig[x]]]); 67                                     lt(x);lt(x); 68                                end; 69                    end; 70           end; 71 procedure ins(var x:longint;y:longint);inline; 72           begin 73                if x=0 then 74                   begin 75                        x:=y; 76                        exit; 77                   end; 78                if a[y]<=a[x] then 79                   begin 80                        ins(lef[x],y); 81                        c[x]:=c[lef[x]]+c[rig[x]]+a[x]; 82                        b[x]:=b[lef[x]]+b[rig[x]]+1; 83                   end 84                else 85                    begin 86                         ins(rig[x],y); 87                         c[x]:=c[lef[x]]+c[rig[x]]+a[x]; 88                         b[x]:=b[lef[x]]+b[rig[x]]+1; 89                    end; 90           end; 91 function getrank(x,y:longint):longint;inline; 92          begin 93               if x=0 then exit(-1); 94               if a[x]=y then exit(b[lef[x]]+1); 95               if y
     
      0 then inc(l,a[head]*b[lef[head]]-c[lef[head]]);146               if rig[head]<>0 then inc(l,c[rig[head]]-a[head]*b[rig[head]]);147               if l