题目传送门
Mayor’s posters
题目大意
n（n<=10000) 个人依次贴海报,给出每张海报所贴的范围
l
i
，
r
i
（
1
<
=
l
i
<
=
r
i
<
=
10000000
)
l_i，r_i（1<=l_i<=r_i<=10000000)
li，ri（1<=li<=ri<=10000000) 。求出最后还能看见多少张海报。（海报只露出部分也算）
思路
首先注意到数据范围
l
i
，
r
i
（
1
<
=
l
i
<
=
r
i
<
=
10000000
)
l_i，r_i（1<=l_i<=r_i<=10000000)
li，ri（1<=li<=ri<=10000000)，显然直接开数组存会TLE或者MLE 所以需要离散化处理一下数据，处理的时候记得非相邻区间查一个值进去 离散化之后就是线段树处理了，每次更新数据时（即为贴上新海报的时候）值为
i
i
i，可以在懒惰标记下沉的时候将颜色传进去，最后查询整个线段树记录叶节点的颜色即可 具体操作可以参考大佬的解释：线段树懒惰标记操作
AC Code
#include<vector>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std
;
#define ll long long
const int N
=2e5+9;
int flag
[N
];
struct node
{
int x
, y
;
}a
[N
];
struct segtree
{
int v
, colour
;
}tr
[N
<<2];
inline int read()
{
int ans
=0;
char last
=' ',ch
=getchar();
while(ch
<'0'||ch
>'9') last
=ch
,ch
=getchar();
while(ch
>='0'&&ch
<='9') ans
=ans
*10+ch
-'0',ch
=getchar();
if(last
=='-') ans
=-ans
;
return ans
;
}
inline int lc(int p
) {return p
<<1;}
inline int rc(int p
) {return p
<<1|1;}
inline void build(int k
, int l
, int r
){
tr
[k
].colour
=0;
if(l
==r
) return ;
int mid
=(l
+r
)>>1;
build(lc(k
), l
, mid
);
build(rc(k
), mid
+1, r
);
}
inline void f(int p
, int k
){
tr
[p
].colour
=k
;
}
inline void push_down(int p
){
f(lc(p
), tr
[p
].colour
);
f(rc(p
), tr
[p
].colour
);
tr
[p
].colour
=0;
}
inline void updata(int p
, int l
, int r
, int x
, int y
, int k
){
if(x
>r
|| y
<l
) return ;
if(l
<=x
&& y
<=r
){
tr
[p
].colour
=k
;
return ;
}
int mid
=(x
+y
)>>1;
if(tr
[p
].colour
) push_down(p
);
updata(lc(p
), l
, r
, x
, mid
, k
);
updata(rc(p
), l
, r
, mid
+1, y
, k
);
}
inline void query(int p
, int l
, int r
, int x
, int y
){
if(x
==y
&& tr
[p
].colour
==0) return ;
if(tr
[p
].colour
) {flag
[tr
[p
].colour
]=1; return ;}
int mid
=(x
+y
)>>1;
query(lc(p
), l
, r
, x
, mid
);
query(rc(p
), l
, r
, mid
+1, y
);
}
int T
, n
;
vector
<int>v
;
int val
[N
];
int main(){
cin
>>T
;
while(T
--){
memset(flag
, 0, sizeof(flag
));
v
.clear();
n
=read();
for(int i
=1; i
<=n
; i
++){
a
[i
].x
=read(); a
[i
].y
=read();
v
.push_back(a
[i
].x
);
v
.push_back(a
[i
].y
);
}
sort(v
.begin(), v
.end());
v
.erase(unique(v
.begin(), v
.end()), v
.end());
val
[0]=1;
int k
=1;
for(int i
=1; i
<v
.size(); i
++){
if(v
[i
]-v
[i
-1]==1) k
++;
else k
+=2;
val
[i
]=k
;
}
build(1,1,N
);
for(int i
=1; i
<=n
; i
++){
a
[i
].x
=val
[(lower_bound(v
.begin(), v
.end(), a
[i
].x
)-v
.begin())];
a
[i
].y
=val
[(lower_bound(v
.begin(), v
.end(), a
[i
].y
)-v
.begin())];
updata(1,a
[i
].x
,a
[i
].y
,1,N
,i
);
}
query(1,1,N
,1,N
);
int ans
=0;
for(int i
=1; i
<=n
; i
++) if(flag
[i
]) ans
++;
cout
<<ans
<<endl
;
}
return 0;
}
