【BZOJ 2212】【POI 2011】Tree Rotations

http://www.lydsy.com/JudgeOnline/problem.php?id=2212

自下而上贪心。

需要用权值线段树来记录一个权值区间内的出现次数。

合并线段树时统计逆序对的信息就可以了。

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 200003;

int v[N << 1], ch[N << 1][2], n, cnt = 0, root[N << 1];

void read_tree(int x) {

	scanf("%d", &v[x]);

	if (v[x] == 0) {

		ch[x][0] = ++cnt; read_tree(cnt);

		ch[x][1] = ++cnt; read_tree(cnt);

	}

}

int tot = 0;

struct node {

	int sum, l, r;

} T[N * 30];

void update(int &rt, int l, int r, int key) {

	rt = ++tot;

	++T[tot].sum;

	if (l == r) return;

	int mid = (l + r) >> 1;

	if (key <= mid)

		update(T[tot].l, l, mid, key);

	else

		update(T[tot].r, mid + 1, r, key);

}

ll sum1, sum2, ans = 0;

int merge(int x, int y) {

	if (x == 0 || y == 0) return x + y;

	sum1 += 1ll * T[T[x].l].sum * T[T[y].r].sum;

	sum2 += 1ll * T[T[x].r].sum * T[T[y].l].sum;

	T[x].l = merge(T[x].l, T[y].l);

	T[x].r = merge(T[x].r, T[y].r);

	T[x].sum = T[T[x].l].sum + T[T[x].r].sum;

	return x;

}

void solve(int x) {

	if (v[x]) return;

	solve(ch[x][0]), solve(ch[x][1]);

	sum1 = sum2 = 0;

	root[x] = merge(root[ch[x][0]], root[ch[x][1]]);

	ans += min(sum1, sum2);

}

int main() {

	scanf("%d", &n);

	++cnt; read_tree(cnt);

	for (int i = 1; i <= cnt; ++i)

		if (v[i])

			update(root[i], 1, n, v[i]);

	solve(1);

	printf("%lld\n", ans);

	return 0;

}

巴特西

【BZOJ 2212】【POI 2011】Tree Rotations

最新文章

热门文章