laekov

退役了之后智商下降严重啊。今天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);

}