bzoj1367 [Baltic2004]sequence 左偏树+贪心

题目传送门

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

题解

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

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

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

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

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

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

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

时间复杂度 \(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;

}

巴特西

bzoj1367 [Baltic2004]sequence 左偏树+贪心

题目传送门

题解

最新文章

热门文章