线段树实现起来细节有点多，用了multiset
参考了一下大佬的题解
排序时需要注意顺序问题
- 先左后右
- 先入后出
- 入边从高到低
- 出边从低到高
感性理解一下即可
加入边时考虑是否会变高
删除边时考虑是否会变低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
using namespace std;
const int N=200050;
struct node{int x,h,opt;}t[N<<2];
struct dot{int x,y;}ans[N<<2];
int n,cnt=0;
multiset<int> S;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') {t=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*t;
}
bool cmp(node a,node b)
{
if (a.x!=b.x) return a.x<b.x;
if (a.opt!=b.opt) return a.opt>b.opt;
if (a.opt==1) return a.h>b.h;
if (a.opt==-1) return a.h<b.h;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int h=read(),l=read(),r=read();
t[i]=(node){l,h,1};
t[i+n]=(node){r,h,-1};
}
n<<=1;
sort(t+1,t+n+1,cmp);
S.insert(0);
for(int i=1;i<=n;i++)
{
int H=*S.rbegin();
if (t[i].opt==1)
{
if (t[i].h>H)
{
ans[++cnt]=(dot){t[i].x,H};
ans[++cnt]=(dot){t[i].x,t[i].h};
S.insert(t[i].h);
}
else S.insert(t[i].h);
}
if (t[i].opt==-1)
{
if (t[i].h==H&&S.count(H)==1)
{
S.erase(H);
ans[++cnt]=(dot){t[i].x,H};
ans[++cnt]=(dot){t[i].x,*S.rbegin()};
}
else S.erase(S.find(t[i].h));
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%d %d\n",ans[i].x,ans[i].y);
return 0;
}