【Baltic2004】sequence

Source and Judge

Baltic2004
bzoj1367

Record

3h

Analysis

请先思考后再展开

首先让ai递增等价于让bi=ai-i不递减
前置知识:

  1. 对于一个序列,如果变成相同的数,那么变成中位数的绝对值代价最小
  2. 两段序列合并的中位数,显然在两边中位数的值域区间内
    然后我们现在要寻找最小代价,肯定要在多个最优解中尽量找一个最容易算的形式,同理,我们说的中位数是指第 $\lceil \frac{n}{2} \rceil$ 小的数
    然后我们的思路主要是,对于一个不递增的序列,变成不递减的最小代价方案中一定有变成中位数

那么做法非常容易,每次加入一个数,作为一个区间和上一个区间比较,如果比上个区间的中位数小或相等,则合并两段区间,并用新的中位数作为这段区间的目标值,并不断往前这样做
然后实现的话,用可并堆(如左偏树)是nlogn,否则是log方,堆顶就是中位数那样维护,两边都是奇数长度时缩1即可

但是这个做法的正确性呢?hyh的论文有一段没看懂,DraZxlNDdt的博客也有一段没看懂,捣鼓了几天(其实主要是过年巨颓废)才想出来(神仙写的东西依旧没看懂;哦说不定还是伪证?)

第一点,两段区间的中位数不递增的话(不仅是内部递减的情况),合并为新序列的中位数
设前一段的中位数为u,后一段的中位数为v
设中间的编号为t,设某个最优方案为b,显然只考虑 $b_t,v \leq b_{t+1},u$ 否则没必要说下去了(例如左边如果比u大,改为全部u不会更差,递增性也保证了)

所以可以改为 $b_t,b_t,…,b_{t+1},b_{t+1}$
此时已经非常棒了,然而还是不好求,考虑进一步转化,这里就比较容易了
因为两边分别的代价是越接近中位数越小,显然两边不同是亏的,数学证明的话也很好推,分类讨论一下即可
所以两边相同,然后显然取为中位数

第二点,新序列的中位数在保存的数中
这个你会经历多个过程,首先你想着维护中位数可以log方,然后你可能会想把中位数放在堆顶,感觉很对,然后又想想万一中位数不在两个堆中呢?再仔细想想又可以证明不会出现这种情况(我觉得这个很难啊……)
这需要我们仔细思考现在做法的细节
我们现在担心的是,新的中位数出现在右边,而且比右边中位数大
合并的时候一定是 $L_{mid} \leq R_{mid},L_{mid} \leq R_{mid_old}$
然后因为只有一个数,显然 $mid_old+1=mid$
然后因为新的中位数在它们之间,所以如果比右边中位数大的话,不会出现在右边,只会在左边
画画图就能理解了,关键是这个细节是否能在证明的时候想到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
ll myabs(ll x) {return x>0?x:-x;}
const int MAX_N=1e6+10;
int a[MAX_N];
struct Nod{int ls,rs,dis,key;Nod(){ls=rs=0;dis=-1;key=-INF;}}p[MAX_N];
int merg(int a,int b)
{
if(a==0 or b==0) return a+b;
if(p[a].key<p[b].key) swap(a,b);
p[a].rs=merg(p[a].rs,b);
if(p[p[a].ls].dis<p[p[a].rs].dis) swap(p[a].ls,p[a].rs);
p[a].dis=p[p[a].rs].dis+1;
return a;
}
int cnt=0,rt[MAX_N],right[MAX_N],siz[MAX_N];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=i;
for(int i=1;i<=n;i++)
{
siz[++cnt]=1;rt[cnt]=right[cnt]=i;p[i].key=a[i];p[i].dis=0;
while(p[rt[cnt-1]].key>=p[rt[cnt]].key)
{
cnt--;right[cnt]=right[cnt+1];
rt[cnt]=merg(rt[cnt],rt[cnt+1]);siz[cnt]+=siz[cnt+1];
while(siz[cnt]*2>right[cnt]-right[cnt-1]+1)//delete
rt[cnt]=merg(p[rt[cnt]].ls,p[rt[cnt]].rs),siz[cnt]--;
}
}
ll ans=0;
for(int i=1;i<=cnt;i++)
for(int j=right[i-1]+1;j<=right[i];j++)
ans+=myabs(a[j]-p[rt[i]].key);
printf("%lld",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a3ae.html
转载请注明出处,谢谢!