洛谷P3521 ROT-Tree Rotations

传送门

题目描述

给定一颗有 nn 个叶节点的二叉树。每个叶节点都有一个权值 p_ip i
​（注意，根不是叶节点），所有叶节点的权值构成了一个 1 \sim n1∼n 的排列。
对于这棵二叉树的任何一个结点，保证其要么是叶节点，要么左右两个孩子都存在。
现在你可以任选一些节点，交换这些节点的左右子树。
在最终的树上，按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 nn 的排列，你需要最小化这个排列的逆序对数。

输入格式

第一行是一个整数 nn，表示树的叶节点个数。
接下来若干行，使用递归的形式来读入这棵树，读入任意一个子树的信息时，初始时读入其根节点。对于一个结点 uu，首先有一行一个整数 xx。

若 x \neq 0x

=0，则表示 uu 是一个叶节点，其权值为 xx。
若 x = 0x=0，则表示 uu 不是叶节点，则接下来若干行读入其左子树信息，左子树读入结束后接下来若干行读入其右子树信息。

输出格式

输出一行一个整数表示最小的逆序对数。

输入输出样例
输入 #1复制
3
0
0
3
1
2
输出 #1复制
1
说明/提示
样例 1 解释
下图中，左图是初始读入的树，右图是操作后的树。

数据规模与约定

对于 30%30% 的数据，保证 n \leq 5 \times 10^3n≤5×10
3
。
对于 100%100% 的数据，保证 2 \leq n \leq 2 \times 10^52≤n≤2×10
5
， 0 \leq x \leq n0≤x≤n，所有叶节点的权值是一个 1 \sim n1∼n 的排列。
提示
请注意，nn 不是树的结点个数。

上代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef int mainint;
typedef double db;
typedef long long ll;
#define il inline 
#define pii pair<ll,int>
#define mp make_pair
#define B cout << "breakpoint" << endl;
#define O(x) cout << #x << "  " << x << endl;
inline int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') op = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        (ans *= 10) += ch - '0';
        ch = getchar();
    }
    return ans * op;
}
const int maxn = 5e5 + 5;
int ls[maxn],rs[maxn],tot;
int sum[maxn];
int n;
ll ans1,ans2,ans;
int st[maxn],top;
il void trash(int i)
{
	ls[i] = rs[i] = sum[i] = 0; st[++top] = i;
}
il void up(int i)
{
	sum[i] = sum[ls[i]] + sum[rs[i]];
}
void update(int &i,int l,int r,int x,int d)
{
	if(!i) i = !top ? ++tot : st[top--];
	if(l == r && l == x)
	{
		sum[i] += d;
		return;
	}
	int mid = l + r >> 1;
	if(x <= mid) update(ls[i],l,mid,x,d);
	else update(rs[i],mid + 1,r,x,d);
	up(i);
}
void merge(int &lx,int rx)
{
	if(!lx || !rx)  
	{ 
		lx = lx + rx; 
		//if(rx) trash(rx);
		return; 
	}
	sum[lx] = sum[lx] + sum[rx];
	ans1 += 1ll * sum[rs[lx]] * sum[ls[rx]];
	ans2 += 1ll * sum[ls[lx]] * sum[rs[rx]];
	merge(ls[lx],ls[rx]);
	merge(rs[lx],rs[rx]);
	trash(rx);
}
void solve(int &x)
{
	int t = read();
	int leftson,rightson;
	x = 0;
	if(t)
		update(x,1,n,t,1);
	else
	{
		solve(leftson); solve(rightson);
		ans1 = ans2 = 0;
		x = leftson; 
		merge(x,rightson);
		ans += min(ans1,ans2);
	}
}
int main()
{
	n = read();
	int x = 0;
	solve(x);
	cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99