描述

小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~

这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？

于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？

提示一：正确的认识信息量

提示二：小Hi大讲堂之线段树的节点意义

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第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，表示总共有多少张海报能被看到。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 #define CH for(int d=0;d<2;d++)if(ch[d])

 #define lson x->ch[0],L,M

 #define rson x->ch[1],M+1,R

 using namespace std;

 const int maxn=+,maxnode=+,inf=-1u>>;

 struct node{

     node*ch[];int siz;int t;

     void addt(int a){t=a;return;}

     void down(){if(t){CH{ch[d]->addt(t);}t=;}return;}

 }seg[maxnode],*nodecnt=seg,*root;

 struct data{int L,R;}d[maxn];

 int n,num[maxn],A[maxn],ql,qr,cv,pos;bool ans[maxn];

 void build(node*&x=root,int L=,int R=n<<){

     x=nodecnt++;int M=L+R>>;if(L==R)x->t=;

     else build(lson),build(rson);x->siz=R-L+;return;

 }

 void update(node*&x=root,int L=,int R=n<<){

     if(ql<=L&&R<=qr)x->addt(cv);

     else{int M=L+R>>;x->down();

         if(ql<=M)update(lson);

         if(qr>M)update(rson);

     }return;

 }

 void query(node*x=root,int L=,int R=n<<){

     if(!x)return;

     if(x->t)ans[x->t]=true;

     else{int M=L+R>>;

         query(lson);query(rson);

     }return;

 }

 inline int read(){

     int x=,sig=;char ch=getchar();

     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;

     for(;isdigit(ch);ch=getchar())x=*x+ch-'';

     return sig?x:-x;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 void init(){

     n=read();read();build();int x,y;

     for(int i=;i<=n;i++)x=num[i<<]=read(),y=num[(i<<)|]=read(),d[i]=(data){x,y};

     sort(num+,num+n*+);int L=unique(num+,num+n*+)-num;

     for(int i=;i<=n;i++){

         ql=upper_bound(num+,num+L,d[i].L)-num-;

         qr=upper_bound(num+,num+L,d[i].R)-num-;//attention

         cv=i;update();

     }query();int res=;

     for(int i=;i<=(n<<);i++)if(ans[i])res++;write(res);

     return;

 }

 void work(){

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}