---

题目描述

桌子上零散地按照后先后顺序放着若干个盒子，盒子都平行于墙。桌子的后方是一堵墙。如图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远。

---

输入格式

第1行：3个整数L，R，N。-100000 <=L<=R<= 100000，表示墙所在的区间；1<=N<=100000，表示盒子的个数 接下来N行，每行2个整数BL, BR，-100000 <=BL<=BR<= 100000，表示一个盒子的左、右端点

---

输出格式

输出仅为一个整数M，表示可看到的盒子个数。

---

样例数据

样例输入

1 10 4 3 5 1 4 2 6 7 8

样例输出

3

---

题目分析

统计标记种类（区间修改区间查询） 我的做法很神奇 直接给区间一个颜色（序号不同颜色不同） 然后查到了就Hash颜色 最后统计Hash 别忘了加偏移量

---

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=600000; int Hash[maxn]; struct Tree { //修改区间 查询区间 int left,right,data; }; struct Segment_Tree { //统计标记种类 Tree tree[maxn*4]; void build(int index,int Left,int Right) { tree[index].left=Left; tree[index].right=Right; tree[index].data=0; if(Left==Right)return; int mid=(Left+Right)/2; build(2*index,Left,mid); build(2*index+1,mid+1,Right); } void push_down(int index) { if(tree[index].data>=0) { tree[index*2].data=tree[index*2+1].data=tree[index].data; tree[index].data=-1; } } void modify(int index,int Left,int Right,int color) { if(Right<tree[index].left||Left>tree[index].right)return; //不相交 if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含 tree[index].data=color; return; } push_down(index); modify(index*2,Left,Right,color); modify(index*2+1,Left,Right,color); } void Query(int index,int Left,int Right) { if(Right<tree[index].left||Left>tree[index].right)return; //不相交 if(tree[index].data==0)return; if(tree[index].data>0) { Hash[tree[index].data]=1; return; } Query(index*2,Left,Right); Query(index*2+1,Left,Right); } }; Segment_Tree st; int Left,Right,n,Delta; int main() { Left=Get_Int(); Delta=Left-1; Left-=Delta; Right=Get_Int()-Delta-1; st.build(1,Left,Right); n=Get_Int(); for(int i=1; i<=n; i++) { int l=Get_Int()-Delta,r=Get_Int()-Delta-1; st.modify(1,l,r,i); } st.Query(1,Left,Right); int sum=0; for(int i=1; i<=n; i++) if(Hash[i])sum++; printf("%d\n",sum); return 0; }

---