由于坐标可能很大，此时需要离散化，将值转化为对应的坐标。
#include<stdio.h> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 200010 int mark[maxn*2],sum[maxn*4],ans; struct Node { int x; int y; }node[maxn]; int num[maxn*2]; void pushup(int rt) { if(sum[rt<<1]&&sum[rt<<1|1]) sum[rt]=1; else sum[rt]=0; } void build(int l,int r,int rt) { if(l==r) { sum[rt]=0; return ; } int m=(l+r)/2; build(lson); build(rson); pushup(rt); } void updata(int L,int R,int l,int r,int rt,int c) { if(sum[rt]) return ; if(l>=L&&R>=r) { sum[rt]=1; if(!mark[c]) { mark[c]=1; ans++; return ; } return ; } int m=(l+r)/2; if(m>=L) updata(L,R,lson,c); if(R>m) updata(L,R,rson,c); pushup(rt); } int find(int val,int x,int y) { int l=x; int r=y; int m; while(l<=r) { m=(l+r)/2; if(num[m]==val) return m; else if(num[m]>val) r=m-1; else l=m+1; } return -1; } int main() { int i,t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); int m=1; for(i=0;i<n;i++) { scanf("%d%d",&node[i].x,&node[i].y); num[m++]=node[i].x; num[m++]=node[i].y; } sort(num+1,num+m); int k=2; //去重复 for(i=2;i<m;i++) { if(num[i]!=num[i-1]) num[k++]=num[i]; } //防止相邻的出现问题 for(i=k-1;i>1;i--) { if(num[i]!=num[i-1]+1) num[k++]=num[i-1]+1; } memset(mark,0,sizeof(mark)); sort(num+1,num+k); build(1,k-1,1); ans=0; for(i=n-1;i>=0;i--)//倒着贴 { int ll=find(node[i].x,1,k-1); int rr=find(node[i].y,1,k-1); updata(ll,rr,1,k-1,1,i+1); } printf("%d ",ans); } }