左偏树维护动态区间中位数。
传送门 P4331 BalticOI 2004 Sequence 数字序列。
Solution
1
我的思路和题解前半部分完全重合了（（
如果按照单调不增去分割 \(a\) 序列的话，对于每一段我们能很简单地得出它的最佳答案：中位数。
发现严格单调很难做，很难拿捏，考虑对 \(a\) 序列的每一项都进行相应的处理，弱化题目。
那么对这些区间单调不增的要求呢？（假如我们先考虑弱化版问题。）
根据我自己的推论，如果区间取值上浮/下沉，所花的代价和区间长度以及区间受影响的值与浮沉值的偏差大小有关。
说的很抽象。但确实这个代价很难算。
那如何去调整区间与区间之间的取值呢？
2
好，根据题解，我们可以把这个问题转化成原题的二次问题。
我当时貌似就是因为发现了这里是原题的二次问题而被搞了心态决定放弃推了。
假定现在有个 \(a'\) 序列，每项的值对应着它在原序列的所在区间的中位数。
那么我们现在就要求出一个序列 \(b'\)，满足它每项的值与对应在 \(a'\) 序列的值之差的绝对值的总和最小。
总和最小是因为 \(a'\) 已经是不满足单调的情况下的最优解了，那合法的最优解不就是和不合法的最优解多花代价最少的方案吗。
且序列 \(b'\) 得是单调不降的。
然后这就是个原题。
嗯。然后对原题重新做一遍。
3
是的，这样会发现此题貌似无止境下去了。
但是进一步地思考，会发现问题的本质实际上就是不断地将两个关系不合法的相邻区间合并并且给他们的答案取中位数。
知道了问题的本质，那如何着手处理这个问题呢？
如果直接按照找到区间然后不断处理区间之间关系的话，这个最外层的复杂度显然并非线性的，且很难处理。
我们的理想状态当然是最外层是线性的。
考虑通过线性的方式解决，将项一个一个按序加进来。不妨将这个数视为一个独立区间，则：
-
它并不与上一个区间成不降序列：合并两者并取中位数；
-
成不降序列：不对它进行操作。
如何证明这样是满足我们要求的做法呢？
其实和刚刚的思路是同理的，可以按照刚刚的证明方法重证一遍。
所以做法大致是这样的：
按序遍历 \(n\) 个点，对于每个点，让它成为独立的区间，然后加进来，
如果它不和上一个区间成不降关系的话，那么就合并它们两个，然后这个区间的答案就取这个大区间的中位数（数会被修改）。
然后往前面回溯，对于不满足条件的两个区间都合并，直到碰到一个不用修改的为止。
然后我们可以使用左偏树维护中位数了。
根据黄源河大佬所述，时复可被左偏树优化至 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define T L.t
const int maxn = 1e6 + 5;
int n, A[maxn], b[maxn];
int ans, tot;
struct tree{
int vl, dis, ls, rs;
};
struct node{
int rt, l, r, sz, w;
}e[maxn];
struct Leftist_Tree{
tree t[maxn]; //int rt;
inline void up(int x){
t[x].dis = t[x].rs ? t[t[x].rs].dis + 1 : 0;
}
inline int merge(int a, int b){
if(!a or !b) return a + b;
if(A[a] < A[b]) swap(a, b);
t[a].rs = merge(t[a].rs, b);
if(t[t[a].ls].dis <= t[t[a].rs].dis)
swap(t[a].ls, t[a].rs);
up(a); return a;
}
}L;
signed main(){
scanf("%lld", &n);
rep(i, 1, n) scanf("%lld", &A[i]), A[i] -= i;
rep(i, 1, n){
e[++tot] = {i, i, i, 1, A[i]};
while(tot > 1 and e[tot].w < e[tot - 1].w){
tot -= 1;
e[tot].rt = L.merge(e[tot].rt, e[tot + 1].rt);
e[tot].r = e[tot + 1].r, e[tot].sz += e[tot + 1].sz;
while(e[tot].sz * 2 > e[tot].r - e[tot].l + 2){
e[tot].sz -= 1, e[tot].rt = L.merge(T[e[tot].rt].ls, T[e[tot].rt].rs);
}
e[tot].w = A[e[tot].rt];
}
}
rep(i, 1, tot) rep(j, e[i].l, e[i].r){
b[j] = e[i].w, ans += abs(A[j] - b[j]);
}
printf("%lld\n", ans);
rep(i, 1, n) printf("%lld ", b[i] + i);
return 0;
}
Thanks for reading.