解题：POI2008 Building blocks

显然我们需要考虑每一个区间，而这个问题显然我们都会做，这不就是这道题么，也就是说假如中位数是$mid$，区间和是$sum$，那么代价就是$\sum\limits_{i=l}^r |mid-num[i]|$

所以现在我们要维护这样的一个数据结构：支持删除/插入一个数，查询中位数和查询区间和

线段树？平衡树？写不来写不来，对顶堆即可解决

维护一个大根堆存区间中较小的一半数，小根堆存区间中较大的一半数，插入时比较一下两个堆的大小和堆顶元素(细节比较多，有一大坨讨论)。查询中位数就非常方便了，直接查询大根堆堆顶。查询区间和的操作也很好做，开两个变量记录一下就好了。唯一有点问题的是如何删除，因为std::priority_queue只能允许我们操作堆顶元素，解决方法一是手写堆，然而我不会，所以我用第二种方法：打标记。注意每次更新前后标记的下放，然后就做完了。

 1 #include<queue>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=100005,M=1000005;
 7 long long num[N],laz[M];
 8 long long n,k,m,l,r,mid;
 9 long long siz1,siz2,sum1,sum2,ans;
10 priority_queue<int> heap1;
11 priority_queue<int,vector<int>,greater<int> > heap2;
12 void Release()
13 {
14     while(!heap1.empty()&&laz[heap1.top()])
15         laz[heap1.top()]--,heap1.pop();
16     while(!heap2.empty()&&laz[heap2.top()])
17         laz[heap2.top()]--,heap2.pop();
18 } 
19 void Push(long long x)
20 {
21     Release();
22     while(siz2&&siz1<m)
23     {
24         long long tpp=heap2.top(); 
25         heap2.pop(); heap1.push(tpp);
26         siz1++,siz2--,sum1+=tpp,sum2-=tpp;
27         Release();
28     }
29     if(!siz1)
30         heap1.push(x),siz1++,sum1+=x;
31     else
32     {
33         Release();
34         if(heap1.top()>x)
35             heap1.push(x),siz1++,sum1+=x;
36         else 
37             heap2.push(x),siz2++,sum2+=x; 
38         Release();
39         while(siz1>m)
40         {
41             long long tpp=heap1.top(); 
42             heap1.pop(); heap2.push(tpp);
43             siz1--,siz2++,sum1-=tpp,sum2+=tpp;
44             Release();
45         }
46         while(siz2&&siz1<m)
47         {
48             long long tpp=heap2.top(); 
49             heap2.pop(); heap1.push(tpp);
50             siz1++,siz2--,sum1+=tpp,sum2-=tpp;
51             Release();
52         }
53     }
54 }
55 void Pop(long long x)
56 {
57     laz[x]++;
58     if(heap1.top()>=x) siz1--,sum1-=x;
59     else siz2--,sum2-=x; Release();
60 }
61 long long cost()
62 {
63     return sum2-sum1+(k&1)*heap1.top();
64 }
65 int main ()
66 {
67     scanf("%lld%lld",&n,&k),m=(k+1)/2;
68     for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
69     for(int i=1;i<=k;i++) Push(num[i]);
70     ans=cost(),l=1,r=k,mid=heap1.top();
71     for(int i=k+1;i<=n;i++)
72     {
73         Pop(num[i-k]),Push(num[i]);
74         if(ans>cost()&&cost()>=0)
75             ans=cost(),l=i-k+1,r=i,mid=heap1.top();
76     }
77     printf("%lld\n",ans);
78     for(int i=1;i<=n;i++)
79         (i>=l&&i<=r)?printf("%lld\n",mid):printf("%lld\n",num[i]);
80     return 0;
81 }

View Code

解题：POI2008 Building blocks

推荐阅读