题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=1367
题解
先考虑条件为要求不下降序列（不是递增）的情况。
那么考虑一段数值相同的子段，这一段相同的数值显然应该是原序列 \(t\) 中对应的位置上的数的中位数。
（不是中位数答案一定比中位数大）
所以问题转化为划分成很多段，每一段的权值是中位数，要求权值不下降。
对于一段，每一次往前扫，只要前面的中位数比它大，那么就合并。
可以用可并堆维护每一段，只保留中位数以下的数。合并左偏树实现即可。
时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 1e6 + 7;
#define lc c[0]
#define rc c[1]
int n, cc;
int a[N], rt[N], s[N], siz[N], siz2[N], st[N];
struct Node { int c[2], v, dis; } t[N];
inline int merge(int o, int p) {
if (!o || !p) return o ^ p;
if (t[o].v < t[p].v) std::swap(o, p);
t[o].rc = merge(t[o].rc, p);
if (t[t[o].lc].dis < t[t[o].rc].dis) std::swap(t[o].lc, t[o].rc);
t[o].dis = t[t[o].rc].dis + 1;
return o;
}
inline void pop(int &o) { o = merge(t[o].lc, t[o].rc); }
inline void work() {
for (int i = 1; i <= n; ++i) {
// dbg("i = %d\n", i);
rt[++cc] = i, t[i].v = a[i], siz[cc] = siz2[cc] = 1, st[cc] = i;
while (cc > 1 && t[rt[cc]].v <= t[rt[cc - 1]].v) {
--cc;
rt[cc] = merge(rt[cc], rt[cc + 1]);
siz[cc] += siz[cc + 1], siz2[cc] += siz2[cc + 1];
while (siz2[cc] > (siz[cc] + 1) / 2) pop(rt[cc]), --siz2[cc];
}
}
ll ans = 0;
st[cc + 1] = n + 1;
for (int i = 1; i <= cc; ++i)
for (int j = st[i]; j < st[i + 1]; ++j) ans += abs(t[rt[i]].v - a[j]);
printf("%lld\n", ans);
}
inline void init() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]), a[i] -= i;
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}