题解
利用线段树进行区间取$max$和单点查询即可。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, len, x[200005], xx[200005], h[100005];
int size, seg[800005] = {0}, tag[800005] = {0}, _a, _b, val;
int node[400005][2], tot = 0;
void init(){
n = read();
for(int i = 0; i < n; ++i)
h[i] = read(), x[i << 1] = read(), x[i << 1 | 1] = read();
memcpy(xx, x, sizeof(xx));
sort(xx, xx + n + n);
len = unique(xx, xx + n + n) - xx;
for(size = 1; size < len; size <<= 1);
}
void pushdown(int id){
if(tag[id]){
seg[id << 1] = max(seg[id << 1], tag[id]);
tag[id << 1] = max(tag[id << 1], tag[id]);
seg[id << 1 | 1] = max(seg[id << 1 | 1], tag[id]);
tag[id << 1 | 1] = max(tag[id << 1 | 1], tag[id]);
tag[id] = 0;
}
}
void update(int id, int l, int r){
if(l > _b || r < _a)return ;
if(l >= _a && r <= _b){
seg[id] = max(seg[id], val);
tag[id] = max(tag[id], val);
return ;
}
pushdown(id);
update(id << 1, l, (l + r) >> 1);
update(id << 1 | 1, (l + r + 1) >> 1, r);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
int query(int id, int l, int r){
if(l > _b || r < _a)return 0;
if(l >= _a && r <= _b)return seg[id];
pushdown(id);
return max(query(id << 1, l, (l + r) >> 1), query(id << 1 | 1, (l + r + 1) >> 1, r));
}
void solve(){
for(int i = 0; i < n; ++i){
_a = lower_bound(xx, xx + len, x[i << 1]) - xx + 1;
_b = lower_bound(xx, xx + len, x[i << 1 | 1]) - xx;
val = h[i];
update(1, 1, size);
}
node[tot][0] = xx[0], node[tot++][1] = 0;
_a = _b = 1;
int h_last = query(1, 1, size);
if(h_last)
node[tot][0] = xx[0], node[tot++][1] = h_last;
for(int i = 1; i < len; ++i){
_a = _b = i + 1;
int h_cur = query(1, 1, size);
if(h_cur != h_last)
node[tot][0] = xx[i], node[tot++][1] = h_last,
node[tot][0] = xx[i], node[tot++][1] = h_cur,
h_last = h_cur;
}
printf("%d\n", tot);
for(int i = 0; i < tot; ++i)
printf("%d %d\n", node[i][0], node[i][1]);
}
int main(){
init();
solve();
return 0;
}