【bzoj1112】[POI2008]砖块Klo

2014年5月27日3,0543

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

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

题解

据说有很多做法,有一些基于h[i]<=10^6

不过平衡树的做法还是比较容易想的

可以这样考虑

首先如果确定了一个区间,我们只需要求出区间中位数,可以枚举区间并在logn的时间内获得中位数

那么我们需要一种数据结构,支持插入删除,以及logn查询区间k大

平衡树可以实现,并且在获得中位数x时得出大/小等于x的数的个数以及和,就可以获得这个区间的最优值

也就是平衡树不仅要维护子树的大小,还要维护权值和

注意开longlong

 

  • 游客2015年4月7日 下午5:54 回复

    在删除操作中,旋转后继续执行的如果是 del(r ,val)或del(l ,val)行不行?

    #1  
    • lyk2015年4月7日 下午8:43 回复

      我发现这样是会WA的,求教神犇这是为什么QAQ

      #11
      • hzwer2015年4月7日 下午8:52 回复
        admin

        自行模拟TAT

        #12