[Link] https://www.acmicpc.net/problem/17131
Lazy propagation with non recursive segment tree. There was no code sample of using lazy propagation with recursive segment tree so I’ll share this code. Hope this help some one.
*Not to using scanf and cin when ios_base::sync_with_stdio(0)(turn off the sync to stdio);
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
100
101
102
103
104
105
106
107
108
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1 << 20;
const int mod = 1e9 + 7;
const int adjust = 2e5;
int n;
int seg[2 * N];
struct point {
int x;
int y;
int idx;
};
vector<point> points;
vector<point> sweep;
void update(int y) {
for(y+=N; y > 0; y>>=1) seg[y]++;
}
int get(int basis) {
int cnt = 0;
for(int l=basis + 1 + N, r = 2*N - 1; l < r; l>>=1, r>>=1) {
if(l & 1) cnt+=seg[l++];
if(r & 1) cnt+=seg[--r];
}
return cnt;
}
void clearSeg() {
for(int i = 0; i < 2*N; i++) seg[i] = 0;
}
bool cmp(point p1, point p2) { return p1.x < p2.x; }
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
point ptmp;
cin >> ptmp.x >> ptmp.y;
ptmp.idx = i;
ptmp.y += adjust;
points.push_back(ptmp);
}
sort(points.begin(), points.end(), cmp);
int staging_x = points[0].x;
int left[n], right[n];
vector<vector<point>> x_group;
vector<point> tmp;
for(point p : points) {
if(staging_x != p.x) {
x_group.push_back(tmp);
tmp.clear();
tmp.push_back(p);
staging_x = p.x;
} else tmp.push_back(p);
}
if(tmp.size()) x_group.push_back(tmp);
for(vector<point> vec: x_group) {
for(point p: vec) left[p.idx] = get(p.y);
for(point p: vec) update(p.y);
}
clearSeg();
x_group.clear();
tmp.clear();
staging_x = points.back().x;
for(int i = points.size() - 1; i >= 0; i--) {
point p = points[i];
if(staging_x != p.x) {
x_group.push_back(tmp);
tmp.clear();
tmp.push_back(p);
staging_x = p.x;
} else {
tmp.push_back(p);
}
}
if(tmp.size()) x_group.push_back(tmp);
for(vector<point> vec: x_group) {
for(point p: vec) {
right[p.idx] = get(p.y);
}
for(point p: vec) {
update(p.y);
}
}
long sum = 0;
for(int i = 0; i < n; i++) {
sum = sum + (long)left[i] * right[i];
sum %=mod;
}
cout << sum;
return 0;
}