BZOJ2212或洛谷3521 [POI2011]ROT-Tree Rotations

BZOJ原题链接

洛谷原题链接

线段树合并裸题。

因为交换子树只会对子树内部的逆序对产生影响，所以我们计算交换前的逆序对个数和交换后的个数，取\(\min\)即可。

对每个叶子节点建一棵动态开点线段树，然后向上合并并更新答案。

而逆序对可以在线段树合并的过程中算出来，因为是权值线段树，根据\(mid\)计算贡献即可。

这题洛谷和\(BZOJ\)不卡常，而\(LOJ\)丧心病狂地把每个点开到\(160ms\)，我这份代码需要改成超级快读才能卡过。。

#include<cstdio>

using namespace std;

typedef long long ll;

const int N = 8e6 + 10;

int L[N], R[N], S[N], BT, SEG, n;

ll s, s_1, s_2;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline ll minn(ll x, ll y){ return x < y ? x : y; }

void bu(int &r, int x, int y, int k)

{

	r = ++SEG;

	S[r] = 1;

	if (!(x ^ y))

		return;

	int mid = (x + y) >> 1;

	k <= mid ? bu(L[r], x, mid, k) : bu(R[r], mid + 1, y, k);

}

int merge(int x, int y)

{

	if (!x)

		return y;

	if (!y || !(x ^ y))

		return x;

	s_1 += 1LL * S[R[x]] * S[L[y]];

	s_2 += 1LL * S[L[x]] * S[R[y]];

	L[x] = merge(L[x], L[y]);

	R[x] = merge(R[x], R[y]);

	S[x] = S[L[x]] + S[R[x]];

	return x;

}

int dfs()

{

	int r, x, y, ro = 0;

	r = re();

	if (r)

	{

		bu(ro, 1, n, r);

		return ro;

	}

	x = dfs();

	y = dfs();

	s_1 = s_2 = 0;

	ro = merge(x, y);

	s += minn(s_1, s_2);

	return ro;

}

int main()

{

	n = re();

	dfs();

	printf("%lld", s);

	return 0;

}

巴特西

BZOJ2212或洛谷3521 [POI2011]ROT-Tree Rotations

BZOJ原题链接

洛谷原题链接

最新文章

热门文章