Mayor’s posters POJ - 2528
这是一个线段树的题目，不过要离散化，而离散化是一个板子，但是这个离散化和之前的离散化有点不一样，这个离散化后还要处理离散化后的结果，我就不解释了，直接上大佬们的链接，反正我也是看他们的代码打的，我化石太菜了，每天自己再打一遍，不看别人的代码再打一遍，看看还能不能打出来。
大佬的题解链接
下面是本菜鸡的菜鸡程序，几乎照着大佬的代码打的
我离散化的板子，感觉挺好用的
vector<int>v;
int getid(int x)
{return lower_bound(v.begin(),v.end(),x)-v.begin()+1;//得到离散化前值为x的离散值
}
void lisan()
{sort(v.begin(),v.end());//排序v.erase(unique(v.begin(),v.end()),v.end());//去掉排序后重复的树字
}
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<deque>
#include<map>
#include<stdlib.h>
#include<set>
#include<iomanip>
#include<stack>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x & -x
#define fi first
#define ull unsigned long long
#define se second
#define lson (rt<<1)
#define rson (rt<<1|1)
#define endl "\n"
#define bug cout<<"----acac----"<<endl
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
using namespace std;
const int maxn =4e4+10;
const int maxm = 1.5e5+50;
const double eps = 1e-18;
const double inf = 0x3f3f3f3f;
const double lnf = 0x3f3f3f3f3f3f3f3f;
const int mod = 80112002;
const double pi=3.141592653589;
int lsh[maxn<<1],li[maxn<<1],ri[maxn<<1];
vector<int>ve;
int getid(int x)
{return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
}
int sum[maxn<<2],vis[maxn<<2];
int ans=0;
void pushdown(int rt)
{sum[lson]=sum[rt];sum[rson]=sum[rt];sum[rt]=-1;
}
void update(int L,int R,int C,int l,int r,int rt)
{if(L<=l&&r<=R){sum[rt]=C;return;}if(sum[rt]!=-1){pushdown(rt);}int mid=(l+r)>>1;if(mid>=R) update(L,R,C,l,mid,rt<<1);else if(L>mid) update(L,R,C,mid+1,r,rt<<1|1);else update(L,mid,C,l,mid,rt<<1),update(mid+1,R,C,mid+1,r,rt<<1|1);
}
void query(int l,int r,int rt)
{if(!vis[sum[rt]]&&sum[rt]!=-1){ans++;vis[sum[rt]]=1;return ;}if(l==r)return ;if(sum[rt]!=-1){pushdown(rt);}int mid=(l+r)>>1;query(l,mid,lson);query(mid+1,r,rson);
}
int main()
{int T;scanf("%d",&T);while(T--){ms(sum,-1);ms(vis,0);ve.clear();int tot=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++){int u,v;scanf("%d%d",&u,&v);li[i]=u;ri[i]=v;ve.push_back(u);ve.push_back(v);}sort(ve.begin(),ve.end());ve.erase(unique(ve.begin(),ve.end()),ve.end());int len=ve.size();for(int i=1;i<len;i++){if(ve[i]-ve[i-1]>1){ve.push_back(ve[i-1]+1);}}len=ve.size();sort(ve.begin(),ve.end());for(int i=1;i<=n;i++){int x=getid(li[i]);int y=getid(ri[i]);update(x,y,i,1,len,1);}ans=0;query(1,len,1);printf("%d\n",ans);}return 0;
}