ROT-Tree Rotations

Description

给定一棵二叉树, 每个叶子节点有一个权值, 可以任意交换节点的两棵子树, 问产生的最小逆序对数目是多少.

Solution

线段树合并, 维护每个节点的值域线段树, 从叶子到根依次合并两个节点, 合并时求出逆序对.
用指针写费死劲了…
注意要动态开点, 我这是第一次写动态开点.还要删除无用的节点, 防止空间超限.

花时间太多了.交了17遍还没过.

Code

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
// luogu-judger-enable-o2
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 400005;
using std:: min;
namespace {
struct Node {
int val;
Node *ls, *rs;
void clear() { if (ls) ls->clear(); if (rs) rs->clear(); delete this; }
Node () { ls = rs = NULL, val = 0; }
void update() { val = ls ? (rs ? ls->val + rs->val : ls->val) : rs->val; }
void merge(Node* l, Node* r) { val = l ? (r ? l->val + r->val : l->val) : r->val; }
};
class Tree {
Node *root; int n;
void modify(int l, int r, int p, int k, Node* node) {
if (l == r) { node->val += k; return; }
int mid = l + r >> 1;
if (p <= mid) node->ls = new Node(), modify(l, mid, p, k, node->ls);
if (p > mid) node->rs = new Node(), modify(mid + 1, r, p, k, node->rs);
node->update();
}
public:
void clear() { root->clear(); delete this; }
Tree() { root = new Node(); }
void Init(int _, int x) { n = _; modify(1, n, x, 1, root); }
Node* Merge(Node* n1, Node *n2, int& rev1, int &rev2) {
if (not n1 and not n2) return NULL;
Node *r = new Node();
r->merge(n1, n2);
r->ls = Merge(n1 ? n1->ls : NULL, n2 ? n2->ls : NULL, rev1, rev2);
r->rs = Merge(n1 ? n1->rs : NULL, n2 ? n2->rs : NULL, rev1, rev2);
if (not n1 or not n2) return r;
if (n1->rs and n2->ls)
rev1 += n1->rs->val * n2->ls->val;
if (n1->ls and n2->rs)
rev2 += n1->ls->val * n2->rs->val;
return r;
}
Tree* Merge(Tree* T, int& rev) {
Tree* R = new Tree();
delete R->root;
int rev1 = 0, rev2 = 0;
R->root = Merge(this->root, T->root, rev1, rev2);
return rev += min(rev1, rev2), R;
}
};
}
int L[N], R[N], val[N];
Tree* dfs(int u, int n, int& rev) {
if (val[u]) {
Tree* now = new Tree();
now->Init(n, val[u]);
return now;
}
else {
Tree *Ls = dfs(L[u], n, rev), *Rs = dfs(R[u], n, rev);
Tree *r = Ls->Merge(Rs, rev);
Ls->clear(); Rs->clear();
return r;
}
}
int cnt = 1;
void input(int id) {
int t; scanf("%d", &t);
if (not t) {
L[id] = ++cnt, input(cnt);
R[id] = ++cnt, input(cnt);
}
else val[id] = t;
}
int main () {
int n; scanf("%d", &n);
input(1);
int rev = 0;
Tree *Result = dfs(1, cnt, rev);
printf("%d\n", rev);
return 0;
}
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
// luogu-judger-enable-o2
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 400005;
using std:: min;
namespace {
struct Node {
int val;
Node *ls, *rs;
void clear() { if (ls) ls->clear(); if (rs) rs->clear(); delete this; }
Node () { ls = rs = NULL, val = 0; }
void update() { val = ls ? (rs ? ls->val + rs->val : ls->val) : rs->val; }
void merge(Node* l, Node* r) { val = l ? (r ? l->val + r->val : l->val) : r->val; }
};
class Tree {
Node *root; int n;
void modify(int l, int r, int p, int k, Node* node) {
if (l == r) { node->val += k; return; }
int mid = l + r >> 1;
if (p <= mid) node->ls = new Node(), modify(l, mid, p, k, node->ls);
if (p > mid) node->rs = new Node(), modify(mid + 1, r, p, k, node->rs);
node->update();
}
public:
void clear() { root->clear(); delete this; }
Tree() { root = new Node(); }
void Init(int _, int x) { n = _; modify(1, n, x, 1, root); }
Node* Merge(Node* n1, Node *n2, int& rev1, int &rev2) {
if (not n1 and not n2) return NULL;
Node *r;
if (not n1) r = n2;
else if (not n2) r = n1;
else r = new Node();
r->merge(n1, n2);
if (not n1 or not n2) return r;
r->ls = Merge(n1 ? n1->ls : NULL, n2 ? n2->ls : NULL, rev1, rev2);
r->rs = Merge(n1 ? n1->rs : NULL, n2 ? n2->rs : NULL, rev1, rev2);
if (n1->rs and n2->ls)
rev1 += n1->rs->val * n2->ls->val;
if (n1->ls and n2->rs)
rev2 += n1->ls->val * n2->rs->val;
delete n1;
delete n2;
return r;
}
Tree* Merge(Tree* T, int& rev) {
Tree* R = new Tree();
delete R->root;
int rev1 = 0, rev2 = 0;
R->root = Merge(this->root, T->root, rev1, rev2);
return rev += min(rev1, rev2), R;
}
};
}
int L[N], R[N], val[N];
Tree* dfs(int u, int n, int& rev) {
if (val[u]) {
Tree* now = new Tree();
now->Init(n, val[u]);
return now;
}
else {
Tree *Ls = dfs(L[u], n, rev), *Rs = dfs(R[u], n, rev);
Tree *r = Ls->Merge(Rs, rev);
return r;
}
}
int cnt = 1;
void input(int id) {
int t; scanf("%d", &t);
if (not t) {
L[id] = ++cnt, input(cnt);
R[id] = ++cnt, input(cnt);
}
else val[id] = t;
}
int main () {
int n; scanf("%d", &n);
input(1);
int rev = 0;
Tree *Result = dfs(1, cnt, rev);
printf("%d\n", rev);
return 0;
}
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
// luogu-judger-enable-o2
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 800005;
using std:: min;
namespace {
struct Node {
int val;
Node *ls, *rs;
void clear() { if (ls) ls->clear(); if (rs) rs->clear(); delete this; }
Node () { ls = rs = NULL, val = 0; }
void update() { val = ls ? (rs ? ls->val + rs->val : ls->val) : rs->val; }
void merge(Node* l, Node* r) { val = l ? (r ? l->val + r->val : l->val) : r->val; }
};
class Tree {
Node *root; int n;
void modify(int l, int r, int p, int k, Node* node) {
if (l == r) { node->val += k; return; }
int mid = l + r >> 1;
if (p <= mid) node->ls = new Node(), modify(l, mid, p, k, node->ls);
if (p > mid) node->rs = new Node(), modify(mid + 1, r, p, k, node->rs);
node->update();
}
public:
void clear() { root->clear(); delete this; }
Tree() { root = new Node(); }
void Init(int _, int x) { n = _; modify(1, n, x, 1, root); }
Node* Merge(Node *n1, Node *n2, int &rev1, int &rev2) {
if (not n1 and not n2) return NULL;
Node *r = n1 ? n1 : n2;
r->merge(n1, n2);
if (not n1 or not n2) return r;
r->ls = Merge(n1 ? n1->ls : NULL, n2 ? n2->ls : NULL, rev1, rev2);
r->rs = Merge(n1 ? n1->rs : NULL, n2 ? n2->rs : NULL, rev1, rev2);
if (n1->ls and n2->rs)
rev1 += n1->ls->val * n2->rs->val;
if (n2->ls and n1->rs)
rev2 += n2->ls->val * n1->rs->val;
if (n1 and n2) delete n2;
return r;
}
Tree* Merge(Tree* T, int& rev) {
Tree* R = new Tree();
delete R->root;
int rev1 = 0, rev2 = 0;
R->root = Merge(this->root, T->root, rev1, rev2);
return rev += min(rev1, rev2), R;
}
};
}
int L[N], R[N], val[N];
Tree* dfs(int u, int n, int& rev) {
if (val[u]) {
Tree* now = new Tree();
now->Init(n, val[u]);
return now;
}
else {
Tree *Ls = dfs(L[u], n, rev), *Rs = dfs(R[u], n, rev);
Tree *r = Ls->Merge(Rs, rev); delete Ls; delete Rs;
return r;
}
}
int cnt = 1;
void input(int id) {
int t; scanf("%d", &t);
if (not t) {
L[id] = ++cnt, input(cnt);
R[id] = ++cnt, input(cnt);
}
else val[id] = t;
}
int main () {
int n; scanf("%d", &n);
input(1);
int rev = 0;
Tree *Result = dfs(1, cnt, rev);
printf("%d\n", rev);
return 0;
}
-------------本文结束感谢您的阅读-------------