题目描述：
线段树覆盖题目…
题目分析：
离散化+线段树区间更新，最后直接遍历一下整个线段树，把标记全部下放一下，最后O1查询就好了…
题目链接：
BZOJ 5168 Luogu 3740
Ac 代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
const int maxm=
1e5+
100;
int tag[maxm<<
2],ans[maxm],vis[maxm];
int hash[maxm*
6],al[maxm],ar[maxm];
int n,m,cnt,tot;
inline void col(
int o,
int c){tag[o]=c;}
inline void pushdown(
int o)
{
if(tag[o]) col((o<<
1),tag[o]),col((o<<
1)|
1,tag[o]);
tag[o]=
0;
}
void modify(
int o,
int l,
int r,
int ql,
int qr,
int c)
{
if(ql<=l&&r<=qr)
return (
void)(col(o,c));
pushdown(o);
int mid=(l+r)>>
1;
if(ql<=mid) modify((o<<
1),l,mid,ql,qr,c);
if(qr>mid) modify((o<<
1)|
1,mid+
1,r,ql,qr,c);
}
void cover(
int o,
int l,
int r)
{
if(l>=r)
return (
void)(ans[l]=tag[o]);
pushdown(o);
int mid=(l+r)>>
1;
cover((o<<
1),l,mid),cover((o<<
1)|
1,mid+
1,r);
}
int main()
{
scanf(
"%d%d",&n,&m);
for(
int i=
1;i<=m;i++)
{
scanf(
"%d%d",&al[i],&ar[i]);
hash[++tot]=al[i],hash[++tot]=ar[i];
hash[++tot]=al[i]-
1,hash[++tot]=al[i]+
1;
hash[++tot]=ar[i]-
1,hash[++tot]=ar[i]+
1;
}
std::sort(hash+
1,hash+tot+
1);
cnt=
std::unique(hash+
1,hash+tot+
1)-hash-
1;
for(
int i=
1;i<=m;i++)
{
int ql=
std::lower_bound(hash+
1,hash+cnt+
1,al[i])-hash;
int qr=
std::lower_bound(hash+
1,hash+cnt+
1,ar[i])-hash;
modify(
1,
1,cnt,ql,qr,i);
}
int Ans=
0;
vis[
0]=
1;
cover(
1,
1,cnt);
for(
int i=
1;i<=cnt;i++)
if(!vis[ans[i]]) Ans++,vis[ans[i]]=
1;
printf(
"%d\n",Ans);
return 0;
}
