线段树合并

线段树合并是一种比较神奇的技巧.
ROT-Tree Rotations就是一道非常典型的线段树合并的题.
对于树的每个节点都需要维护一棵权值线段树.需要做的就是将两棵权值线段树合并起来并且求出合并后的逆序对.

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
namespace {
struct Node {
int val, rev;
Node *ls, *rs;
void clear() { if (ls) ls->clear(), rs->clear(); delete this; }
void Update() {
val = ls->val + rs->val;
rev = ls->rev + rs->rev;
}
Node () { ls = rs = NULL, val = rev = 0; }
void merge(Node *l, Node *r) {
val = l->val + r->val;
rev = l->rev + r->rev;
}
};
class Tree {
Node *root; int n;
void build(int l, int r, Node *root) {
if (l == r) return ;
int mid = l + r >> 1;
node->ls = new Node(), node->rs = new Node();
build(l, mid, node->ls);
build(mid + 1, r, node->rs);
}
void modify(int l, int r, int p, int k = 1, Node* node) {
if (l == r) node->val += k;
int mid = l + r >> 1;
if (L <= mid) modify(l, mid, p, k, node->ls);
if (R > mid) modify(mid + 1, r, p, k, node->rs);
node->Update();
}
int query(int l, int r, int L, int R, Node *node) {
if (l >= L and r <= R) return node->val;
int mid = l + r >> 1; int res = 0;
if (L <= mid) res += query(l, mid, L, R, node->ls);
if (R > mid) res += query(mid + 1, r, L, R, node->rs);
return res;
}
public:
int Result() { return root->rev; }
void clear() { root->clear(); delete this; }
Tree() { root = new Node(); Reslut = 0; }
void build(int _) { n = _, build(1, n, root); }
void Init(int _, int x) { build(_), modify(1, n, x, root); }
Node* Merge(Node* n1, Node *n2) {
Node *res = new Node();
res->merge(n1, n2);
if (n1->ls and n2->ls)
res->ls = Merge(n1->ls, n2->ls);
if (n1->rs and n2->rs)
res->rs = Merge(n2->ls, n2->rs);
res->Update();
res->rev += n1->rs->val * n2->ls->val;
return res;
}
Tree* Merge(Tree* T) {
Tree* R = new Tree();
R->root = Merge(this->root, T->root);
return R;
}
};
}
Tree* dfs(int u, int n) {
Tree* now;
if (val[u]) {
now = new Tree();
now->build(n, val[u]);
}
else {
Tree *Ls = dfs(L[u], n), *Rs = dfs(R[u], n);
Tree *LHR = Ls->Merge(Rs), *RHL = Rs->Merge(Ls);
if (LHR->Result > RHL->Result) swap(LHR, RHL);
delete RHL; return LHR;
}
}
int main () {
int n; scanf("%d", &n);
input()
}
-------------本文结束感谢您的阅读-------------