智商不够线段树来凑

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

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

对了，stl是个好东西，用对了代码短50行不是问题。
另外说一下，去重后不是在[1,n][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;
}