-
Notifications
You must be signed in to change notification settings - Fork 3
/
merge_sort_tree.cpp
executable file
·96 lines (73 loc) · 1.95 KB
/
merge_sort_tree.cpp
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
/** https://www.spoj.com/problems/KQUERY/
**/
class SegmentTree {
vector <vector <int> > sTree;
vector <int> localArr;
int NP2, oo = 0x3f3f3f3f;
public :
template <class T>
SegmentTree(T _begin, T _end) {
NP2 = 1;
int n = _end - _begin;
while(NP2 < n) NP2 <<= 1;
sTree.assign(NP2 << 1, vector <int> ());
localArr.assign(NP2 + 1, 0);
__typeof(_begin) i = _begin;
for(int j = 1; i != _end; i++, ++j)
localArr[j] = *i;
build(1, 1, NP2);
}
void build(int p, int l, int r) {
if(l == r) {
sTree[p].push_back(localArr[l]);
return;
}
build(left(p), l, mid(l, r));
build(right(p), mid(l, r) + 1, r);
merge(p);
}
int query(int ql, int qr, int k) {
return query(ql, qr, k, 1, 1, NP2);
}
private :
int query(int ql, int qr, int k, int p, int l, int r) {
if(isOutside(ql, qr, l, r))
return 0;
if(isInside(ql, qr, l, r)) {
return sTree[p].end() - upper_bound(sTree[p].begin(), sTree[p].end(), k);
}
return query(ql, qr, k, left(p), l, mid(l, r)) + query(ql, qr, k, right(p), mid(l, r) + 1, r);
}
void merge(int p) {
vector <int> & L = sTree[left(p)];
vector <int> & R = sTree[right(p)];
int l_size = L.size();
int r_size = R.size();
int p_size = l_size + r_size;
L.push_back(INT_MAX);
R.push_back(INT_MAX);
sTree[p].resize(p_size);
for(int k = 0, i = 0, j = 0; k < p_size; ++k)
if(L[i] <= R[j])
sTree[p][k] = L[i], i += (L[i] != INT_MAX);
else
sTree[p][k] = R[j], j += (R[j] != INT_MAX);
L.pop_back();
R.pop_back();
}
inline bool isInside(int ql, int qr, int sl, int sr) {
return (ql <= sl && sr <= qr);
}
inline bool isOutside(int ql, int qr, int sl, int sr) {
return (sr < ql || qr < sl);
}
inline int mid (int l, int r) {
return ((l + r) >> 1);
}
inline int left(int p) {
return (p << 1);
}
inline int right(int p) {
return ((p << 1) | 1);
}
};