离散化是将有用的信息提取出来，在区间很大的时候，用直接用线段树肯定会超时，但由于在区间内很大值是没有用到的，只把有用的区间提取出来再用线段数做就方便多了。
1 #include2 #include 3 #include 4 #include 5 #define lson l,m,rt<<1 6 #define rson m+1,r,rt<<1|1 7 using namespace std; 8 const int MAX = 11111; 9 int col[MAX<<4],li[MAX],ri[MAX],x[MAX*3],ans;10 bool hash[MAX];11 void PushDown(int rt){12 if(col[rt] != -1){13 col[rt<<1] = col[rt<<1|1] = col[rt];14 col[rt] = -1;15 }16 }17 void update(int LL, int RR, int c, int l, int r, int rt){18 if(LL <= l && r <= RR){19 col[rt] = c;20 return;21 }22 PushDown(rt);23 int m = (l+r)>>1;24 if(LL <= m)update(LL,RR,c,lson);25 if(m < RR) update(LL,RR,c,rson);26 }27 void query(int l, int r, int rt){28 if(col[rt] != -1){29 if(!hash[col[rt]])ans++;30 hash[col[rt]] = true;31 return;32 }33 if(l == r)return;34 int m = (l+r)>>1;35 query(lson);36 query(rson);37 }38 int Bin(int key,int len){39 int l = 0, r = len-1;40 while(l <= r){41 int m = (l+r)>>1;42 if(x[m] == key)return m;43 if(x[m] > key)r = m-1;44 else l = m+1;45 }46 return -1;47 }48 int main(){49 int t,n;50 scanf("%d",&t);51 while(t--){52 scanf("%d",&n);53 int nn = 0;54 for(int i = 0; i < n; i ++){55 scanf("%d %d",&li[i],&ri[i]);56 x[nn++] = li[i];x[nn++] = ri[i];57 }58 sort(x,x+nn);59 int m = 1;60 for(int i = 1; i < nn; i ++){61 if(x[i]!=x[i-1])x[m++] = x[i];62 }63 for(int i = m-1; i > 0; i --){64 if(x[i] != x[i-1]+1)x[m++] = x[i-1]+1;65 }66 sort(x,x+m);67 memset(col,-1,sizeof(col));68 for(int i = 0; i < n; i ++){69 int l = Bin(li[i],m);70 int r = Bin(ri[i],m);71 update(l,r,i,0,m,1);72 }73 ans = 0;74 memset(hash,false,sizeof(hash));75 query(0,m,1);76 printf("%d\n",ans);77 }78 return 0;79 }