bzoj1367 [Baltic2004]sequence 左偏树+贪心

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=1367

题解

先考虑条件为要求不下降序列（不是递增）的情况。

那么考虑一段数值相同的子段，这一段相同的数值显然应该是原序列 \(t\) 中对应的位置上的数的中位数。

（不是中位数答案一定比中位数大）

所以问题转化为划分成很多段，每一段的权值是中位数，要求权值不下降。

对于一段，每一次往前扫，只要前面的中位数比它大，那么就合并。

可以用可并堆维护每一段，只保留中位数以下的数。合并左偏树实现即可。

不过题目的要求是上升序列，但是我们求出来的是不下降序列。所以可以把 \(t_i\) 都减去 \(i\)，这样就可以把上升序列转化为不下降序列了。

时间复杂度 \(O(n\log n)\)。

#include

#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 inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template 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 pii;

template 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;
}