给一块最大为10^8单位宽的墙面，贴poster，每个poster都会给出数据 a,b,表示该poster将从第a单位占据到b单位，新贴的poster会覆盖旧的，最多有10^4张poster，求最后贴完，会看到几张poster （哪怕只露出一个单位，也算该poster可见）；
我一看这么大数据，又看了下时间限制只有1s，不科学啊，如果真的按10^8建树不可能过时间啊，而且根据它的空间限制，大概只能建10^7这么大的数组。
后来搜博客发现大家的标题都写着离散化，原来用离散化做这个题目，但是我不会离散化，我想找一篇纯讲离散化的博文来好好研究下，。。。没找到，所以原谅我，这个题目是仔仔细细的分析了别人的原题代码才写出来的，否则我真的不知道怎么弄离散化。
所谓离散化，把a，b所有出现的数字全部排序一遍，新的值就是他们的下标，当然重复的不算，然后每个a，b就会赋予一个更小的值，但完全不影响其功能，由于每个不同值都考虑进去了，所以区间缩小之后，不会出现覆盖混乱，最多是正好全部覆盖。。。。
然后说起这个线段树要维护的，其实就是一个量，该区间是否被覆盖，采取从后往前贴poster，这个跟之前做个一个排队插队的题目同理，从后往前，则状态一定固定了，所以更加方便了，只要判断在已经覆盖了这么多poster的情况下，是否还有空余区间就行了。
话说期间WA了几次不明不白是因为，我忘了用懒惰标记和懒惰更新了，果然好久没写线段树了。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 25010
#define Lson x<<1,l,mid
#define Rson (x<<1|1),mid+1,r using namespace std; struct node {
int val;
int num;
} pos[N];
bool flag;
bool d[N*];
int p[N*];
bool cmp2(node a,node b)
{
if (a.val<b.val) return true;
return false;
}
bool cmp(node a,node b)
{
if (a.num>b.num) return true;
if (a.num==b.num && a.val<b.val) return true;
return false;
}
void getup(int x)
{
if (d[x<<]==true || d[x<<|]==true)
d[x]=true;
else
d[x]=false;
}
void build(int x,int l,int r)
{
d[x]=true;
p[x]=;
if (l==r){
return;
}
int mid=(l+r)>>;
build(Lson);
build(Rson);
getup(x);
}
void pushdown(int x,int l,int r)
{
if (!p[x] || l>=r) return;
d[x<<]=d[x<<|]=false;
p[x<<]=p[x<<|]=p[x];
p[x]=;
}
void query(int L,int R,int x,int l,int r)
{
if (L<=l && r<=R)
{
if (d[x])
{
flag=true;
d[x]=false;
p[x]=;
}
return;
}
if (p[x])
pushdown(x,l,r);
int mid=(l+r)>>;
if (L>mid && d[x<<|]) query(L,R,Rson);
else
if (R<=mid && d[x<<]) query(L,R,Lson);
else
if (L<=mid && R>mid){
if (d[x<<]) query(L,R,Lson);
if (d[x<<|]) query(L,R,Rson);
}
getup(x);
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
int i,j,k;
scanf("%d",&n);
int a,b;
for (i=;i<n;i++)
{
scanf("%d%d",&pos[i<<].val,&pos[i<<|].val);
pos[i<<].num=pos[i<<|].num=i;
}
sort(pos,pos+*n,cmp2);
int cur=,pre=-;
for (j=;j<*n;j++)
{
if (pre!=pos[j].val){
pre=pos[j].val;
pos[j].val=++cur;
}
else{
pos[j].val=cur;
}
//cout<<pre<<" "<<pos[j].val<<endl;
} build(,,cur); sort(pos,pos+*n,cmp);
int ans=;
for (i=;i<n;i++)
{
//cout<<pos[i<<1].val<<" "<<pos[i<<1|1].val<<endl;
flag=false;
query(pos[i<<].val,pos[i<<|].val,,,cur);
if (flag) {ans++;}
}
printf("%d\n",ans);
}
return ;
}