智商不够线段树来凑

虽然是一个差分的裸题,但是线段树也是可以过的。

原来题解有篇动态开点的线段树,不过这道题直接离散化然后用线段树做区间修改即可。

对了,stl是个好东西,用对了代码短50行不是问题。
另外说一下,去重后不是在$[1,n]$中排,而是对问题的不同区间端点排序。

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
#include<touwenjian.h>// 由于每次都卡我头文件,所以我不打了

#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define ls i<<1
#define rs i<<1|1

using namespace std;
int n,m;

struct tree{
int mmx,add;
}t[2001000];

struct que{
int l,r;
}q[200200];
int bj[400400],bt=0;

struct orztree{
//线段树没有什么好讲的,结构体美观大方
inline void pushup(int i)
{
t[i].mmx=max(t[ls].mmx,t[rs].mmx);
return ;
}

inline void pushdown(int i)
{
t[ls].add+=t[i].add;
t[rs].add+=t[i].add;
t[ls].mmx+=t[i].add;
t[rs].mmx+=t[i].add;
t[i].add=0;
}

void change_tree(int i,int l,int r,int x,int y,int tar)
{
if(l>=x&&r<=y)
{
t[i].add+=tar;
t[i].mmx+=tar;
return ;
}
pushdown(i);
int mid=(l+r)/2;
if(x<=mid) change_tree(lson,x,y,tar);
if(y>mid) change_tree(rson,x,y,tar);
pushup(i);
return ;
}
}st;

int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n;
m=n; //这里原来以为是读入n,m,结果看了题才发现只有m
int t1,t2;
for(i=1;i<=m;i++)
{
cin>>t1>>t2;
bj[++bt]=t1;
bj[++bt]=t2;
q[i].l=t1;
q[i].r=t2;
}
sort(bj+1,bj+bt+1);
//一定要注意-1
bt=unique(bj+1,bj+bt+1)-bj-1;
for(i=1;i<=m;i++)
{
int t1=lower_bound(bj+1,bj+bt+1,q[i].l)-bj;
int t2=lower_bound(bj+1,bj+bt+1,q[i].r)-bj;
st.change_tree(1,1,bt,t1,t2,1);
}
//t[1].mmx即为整个区间同时要看的电视的数量最大值
if(t[1].mmx>2) cout<<"NO";
else cout<<"YES";
return 0;
}