时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~
这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？
于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。
每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，其中第i+1行为两个整数a_i, b_i，表示第i张海报所贴的区间为[a_i, b_i]。
对于100%的数据，满足N<=10^5，L<=10^9，0<=a_i<b_i<=L。
输出
对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。
- 样例输入
-
5 10
4 10
0 2
1 6
5 9
3 4 - 样例输出
-
5
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=;
struct Node{
int color;//0表示没有贴海报,1表示贴有混合海报
int l,r;
}a[MAXN*];
struct Query{
int l,r;
}qer[MAXN];
int n,L;
int hax[MAXN],cnt;
void build(int rt,int l,int r)
{
a[rt].l=l;
a[rt].r=r;
if(l==r)
{
a[rt].color=;
return ;
}
int mid=(l+r)>>;
build(rt<<,l,mid);
build((rt<<)|,mid+,r);
if(a[rt<<].color==a[(rt<<)|].color) a[rt].color=a[rt<<].color;
else a[rt].color=-;
}
void update(int rt,int l,int r,int val)
{
if(a[rt].l==l&&a[rt].r==r)
{
a[rt].color=val;
return ;
}
if(a[rt].color!=&&a[rt].color!=-)
{
a[rt<<].color=a[rt].color;
a[(rt<<)|].color=a[rt].color;
}
int mid=(a[rt].l+a[rt].r)>>;
if(r<=mid)
{
update(rt<<,l,r,val);
}
else if(mid<l)
{
update((rt<<)|,l,r,val);
}
else
{
update(rt<<,l,mid,val);
update((rt<<)|,mid+,r,val);
}
if(a[rt<<].color==a[(rt<<)|].color) a[rt].color=a[rt<<].color;
else a[rt].color=-;
}
int vis[MAXN],res;
void query(int rt,int l,int r)
{
if(a[rt].color==)
{
return ;
}
if(a[rt].l==l&&a[rt].r==r)
{
if(a[rt].color!=-)
{
if(!vis[a[rt].color])
{
vis[a[rt].color]=;
res++;
}
return ;
}
}
if(a[rt].color!=&&a[rt].color!=-)
{
a[rt<<].color=a[rt].color;
a[(rt<<)|].color=a[rt].color;
}
int mid=(a[rt].l+a[rt].r)>>;
query(rt<<,l,mid);
query((rt<<)|,mid+,r);
}
int main()
{
while(scanf("%d%d",&n,&L)!=EOF)
{
cnt=;
res=;
memset(vis,,sizeof(vis));
for(int i=;i<n;i++)
{
scanf("%d%d",&qer[i].l,&qer[i].r);
hax[cnt++]=qer[i].l;
hax[cnt++]=qer[i].r;
}
sort(hax,hax+cnt);
cnt=unique(hax,hax+cnt)-hax;
build(,,cnt);
int col=;
for(int i=;i<n;i++)
{
int l=lower_bound(hax,hax+cnt,qer[i].l)-hax+;
int r=lower_bound(hax,hax+cnt,qer[i].r)-hax;//不需加1
update(,l,r,col);
col++;
}
query(,,cnt);
printf("%d\n",res);
}
return ;
}