学步园

这道线段树题目应该对我离散化数据的思想有了启蒙，直接做必然超时超内存，所以根据虽然l,r范围好大，但给的海报数n<10000比较小，把l,r20000个数据对应到1-20000就压缩了空间，907msAC。

#include<cstdio>
#include<map>
#include<set> 
#include<algorithm>
using namespace std;
map<int,int>mp;
set<int>st; 
int cmp(int a,int b)
{
    return a<b;
}
int a[80010],c[80010],x[10010],y[10010];
void down(int i)
{
     if(c[i])
     {
             c[2*i]=c[2*i+1]=c[i];
             c[i]=0;
     }
} 
void build(int i,int l,int r)
{
     c[i]=0;
     if(l==r)
     return;
     int m=(l+r)>>1;
     build(2*i,l,m);
     build(2*i+1,m+1,r);
}
void ud(int i,int l,int r,int L,int R,int x)
{
     if(l==L&&r==R)
     {
                   c[i]=x;
                   return;
     }
     down(i);
     int mid=(L+R)>>1;
     if(mid>=r)
     ud(2*i,l,r,L,mid,x); 
     else if(mid<l)
     ud(2*i+1,l,r,mid+1,R,x); 
     else
     {
         ud(2*i,l,mid,L,mid,x); 
         ud(2*i+1,mid+1,r,mid+1,R,x);
     }
}
void dfs(int i,int l,int r)       
{
     if(c[i])
     {
             st.insert(c[i]);
             return; 
     }            
     if(l==r)
     return; 
     int m=(l+r)>>1; 
     dfs(2*i,l,m);
     dfs(2*i+1,m+1,r);
} 
int t,n;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
              int n;
              scanf("%d",&n);
              mp.clear();
              st.clear(); 
              int j=0;
              for(int i=1;i<=n;i++)
              {
                      int q,w;
                      scanf("%d%d",&q,&w);
                      x[i]=q,y[i]=w;
                      a[++j]=q;
                      a[++j]=w;
              }
              sort(a+1,a+2*n+1,cmp);
              int z=0;
              for(int i=1;i<=2*n;i++)
              {
                     while(i!=2*n&&a[i]==a[i+1])i++;
                     mp[a[i]]=++z; 
              }
              build(1,1,z);
              for(int i=1;i<=n;i++)
              {
                      ud(1,mp[x[i]],mp[y[i]],1,z,i);
              } 
              dfs(1,1,z); 
              printf("%d\n",st.size());
    }
    return 0;
}