描述
小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
题解：离散线段树好了，标记是要down的！！！
要注意的是[1,2],[2,3],[3,4]是算3张海报，因为海报实际上是一个连续的区间，所以下标为i对应的是[i,i+1]的区间。所以对于区间[a,b]，线段树更新的节点范围是[a,b-1]。还是相当关键的！
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar(' ') 9 #define CH for(int d=0;d<2;d++)if(ch[d]) 10 #define lson x->ch[0],L,M 11 #define rson x->ch[1],M+1,R 12 using namespace std; 13 const int maxn=200000+10,maxnode=400000+10,inf=-1u>>1; 14 struct node{ 15 node*ch[2];int siz;int t; 16 void addt(int a){t=a;return;} 17 void down(){if(t){CH{ch[d]->addt(t);}t=0;}return;} 18 }seg[maxnode],*nodecnt=seg,*root; 19 struct data{int L,R;}d[maxn]; 20 int n,num[maxn],A[maxn],ql,qr,cv,pos;bool ans[maxn]; 21 void build(node*&x=root,int L=1,int R=n<<1){ 22 x=nodecnt++;int M=L+R>>1;if(L==R)x->t=0; 23 else build(lson),build(rson);x->siz=R-L+1;return; 24 } 25 void update(node*&x=root,int L=1,int R=n<<1){ 26 if(ql<=L&&R<=qr)x->addt(cv); 27 else{int M=L+R>>1;x->down(); 28 if(ql<=M)update(lson); 29 if(qr>M)update(rson); 30 }return; 31 } 32 void query(node*x=root,int L=1,int R=n<<1){ 33 if(!x)return; 34 if(x->t)ans[x->t]=true; 35 else{int M=L+R>>1; 36 query(lson);query(rson); 37 }return; 38 } 39 inline int read(){ 40 int x=0,sig=1;char ch=getchar(); 41 for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0; 42 for(;isdigit(ch);ch=getchar())x=10*x+ch-'0'; 43 return sig?x:-x; 44 } 45 inline void write(int x){ 46 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 47 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 48 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 49 } 50 void init(){ 51 n=read();read();build();int x,y; 52 for(int i=1;i<=n;i++)x=num[i<<1]=read(),y=num[(i<<1)|1]=read(),d[i]=(data){x,y}; 53 sort(num+2,num+n*2+1);int L=unique(num+2,num+n*2+1)-num; 54 for(int i=1;i<=n;i++){ 55 ql=upper_bound(num+2,num+L,d[i].L)-num-2; 56 qr=upper_bound(num+2,num+L,d[i].R)-num-3;//attention 57 cv=i;update(); 58 }query();int res=0; 59 for(int i=1;i<=(n<<1);i++)if(ans[i])res++;write(res); 60 return; 61 } 62 void work(){ 63 return; 64 } 65 void print(){ 66 return; 67 } 68 int main(){init();work();print();return 0;}