退役了之后智商下降严重啊。今天bc死惨了。这比较水的题也是去看了题解才反应过来的。
先把序列改成不降。
然后把原来的序列分成一些段，每段的中位数递增。
考虑新加入一个ai，如果它比前一段的中位数小，那么就把它和前一段合并，再拿合并之后的段去和再前一段比较一下。其实我也不能证明为啥是这样，只是感觉比较有道理。我肯定是没救了。
中位数的话用可合并的堆来维护比较方便。orz各种神级堆，然后我还是用的左偏树。
以后树要拿指针写所以代码巨长。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
#define sof(p) ((p)?(p->s):0)
struct node {
int v, s;
node *ls, *rs;
inline void init(int x) {
v = x;
s = 1;
ls = 0;
rs = 0;
}
inline void update() {
s = sof(ls) + sof(rs) + 1;
if (sof(ls) < sof(rs))
swap(ls, rs);
}
};
typedef long long dint;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (long long int)
const int maxn = 1000009;
int n, st[maxn], ts, a[maxn];
dint ans;
node hn[maxn], *ha[maxn], *hb[maxn];
inline node* haMerge(node* p, node* q) {
if (!p)
return q;
else if (!q)
return p;
else if (p-> v > q-> v) {
p-> rs = haMerge(p-> rs, q);
p-> update();
return p;
}
else {
q-> rs = haMerge(q-> rs, p);
q-> update();
return q;
}
}
inline node* haPop(node* &u) {
node* v = u;
if (u)
u = haMerge(u-> ls, u-> rs);
v-> ls = 0;
v-> rs = 0;
v-> s = 1;
return v;
}
inline node* hbMerge(node* p, node* q) {
if (!p)
return q;
else if (!q)
return p;
else if (p-> v < q-> v) {
p-> rs = hbMerge(p-> rs, q);
p-> update();
return p;
}
else {
q-> rs = hbMerge(q-> rs, p);
q-> update();
return q;
}
}
inline node* hbPop(node* &u) {
node* v = u;
if (u)
u = hbMerge(u-> ls, u-> rs);
return v;
}
void hpUnion(int x, int y) {
ha[x] = haMerge(ha[x], ha[y]);
hb[x] = hbMerge(hb[x], hb[y]);
while (sof(ha[x]) > sof(hb[x]) + 1) {
node* u = haPop(ha[x]);
hb[x] = hbMerge(hb[x], u);
}
while (sof(ha[x]) < sof(hb[x])) {
node* u = hbPop(hb[x]);
ha[x] = haMerge(ha[x], u);
}
}
inline int getMid(int x) {
return ha[x]-> v;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(ha, 0, sizeof(ha));
memset(hb, 0, sizeof(hb));
readInt(n);
for (int i = 1; i <= n; ++ i) {
readInt(a[i]);
a[i] -= i;
hn[i]. init(a[i]);
}
ts = 0;
st[0] = 0;
for (int i = 1; i <= n; ++ i) {
++ ts;
st[ts] = i;
ha[ts] = hn + i;
hb[ts] = 0;
while (ts > 1 && getMid(ts) < getMid(ts - 1)) {
hpUnion(ts - 1, ts);
st[-- ts] = i;
}
}
ans = 0;
for (int i = 1; i <= ts; ++ i) {
int m = getMid(i);
for (int j = st[i - 1] + 1; j <= st[i]; ++ j)
ans += abs(_l a[j] - m);
}
printf(lld "\n", ans);
}