n（n<=10000)个人依次贴海报,给出每张海报所贴的范围li,ri (1<=li<=ri<=1e7) 。求出最后还能看见多少张海报。
Input
第一行: 样例个数T
第二行: 贴海报的人n
第三行: 每个人贴海报的范围
接下来n行: 每个人贴海报的范围
Output
对于每一个输入，输出最后可以看到的海报张数。下面这个图是样例解释
Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4
海报张贴的范围是1e7直接线段树是肯定要超时的更别说还多个样例了，但是海报的张数才1e4，所以总的范围内有非常多点是没有用到的，可以把这些点全部省略只保留用到的端点，然后在线段树就方便许多了，然后还有一个问题
先来个样例吧
2
1 5
1 2
4 5
正确答案应该是3，但是直离散化端点后之后求得的是2，在点2和4之间应该还有一段但是离散化端点之后这一段就被省略了,所以我们需要把省略的这一把分再加入离散化里面，只用加一个省略线段之间的任意一点就可以了（如果省略部分长度大于1），这样就能ac啦，这道题数据有点水，不加省略的部分也能ac。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n,t,a[N],l[N],r[N],idx;
vector<int> ve;
struct node
{
int l,r;
int id;//表示将整个区间覆盖的报纸编号，0表示不存在完全覆盖
}tr[N<<4];
void pushdown(int rt)//只保存能完全覆盖的最小区间，就不用pushup了
{
if(tr[rt].id)
{
tr[rt<<1|1].id=tr[rt<<1].id=tr[rt].id;
tr[rt].id=0;//记得清空
}
}
void build(int rt,int l,int r)
{
if(l==r) tr[rt]={l,l,0};
else
{
tr[rt]={l,r};
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
}
void updata(int rt,int l,int r,int d)
{
if(l<=tr[rt].l&&tr[rt].r<=r)
{
tr[rt].id=d;
}
else
{
pushdown(rt);
int mid =tr[rt].l+tr[rt].r>>1;
if(l<=mid) updata(rt<<1,l,r,d);
if(r>mid) updata(rt<<1|1,l,r,d);
}
}
int ans;
bool st[N];
void query(int rt,int l,int r)
{
if(tr[rt].id)
{
if(!st[tr[rt].id])
{
ans++;
st[tr[rt].id]=1;
}
return ;
}
if(tr[rt].l==tr[rt].r) return ;//记得及时结束
pushdown(rt);
int mid=tr[rt].l+tr[rt].r>>1;
if(l<=mid) query(rt<<1,l,r);
if(r>mid) query(rt<<1|1,l,r);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ve.clear();
for(int i=1;i<=n;i++)
{
scanf("%d%d",l+i,r+i);
ve.push_back(l[i]);
ve.push_back(r[i]);
}
sort(ve.begin(),ve.end());
ve.erase(unique(ve.begin(),ve.end()),ve.end());//去重
int sz=ve.size();//一定要加这一步，因为后面遍历的途中ve.size()就在变化，会一直向里面再加多余的点直到MLE
for(int i=1;i<sz;i++)
if(ve[i]-ve[i-1]>1) ve.push_back((ve[i]-1));
sort(ve.begin(),ve.end());
build(1,1,ve.size());
for(int i=1;i<=n;i++)
{
int x=lower_bound(ve.begin(),ve.end(),l[i])-ve.begin()+1;//我想要端点从1开始
int y=lower_bound(ve.begin(),ve.end(),r[i])-ve.begin()+1;
updata(1,x,y,i);
}
ans=0;
memset(st,0,sizeof st);
query(1,1,ve.size());
printf("%d
",ans);
}
return 0;
}