poj 2528Mayor's posters

这个题有个细节，整个区间的长度为10000000，而n最大只有1000，所以我们要进行离散化。
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define maxn 10010
  5 using namespace std;
  6 
  7 bool tab[maxn];
  8 int l[maxn],r[maxn],x[maxn*3],num[maxn*3],tree[maxn*12];
  9 int c,n;
 10 
 11 int binary_search1(int sum)
 12 {
 13     int l=1,r=3*n;
 14     while(l<=r)
 15     {
 16         int mid=(l+r)/2;
 17         if(x[mid]<=sum)
 18             l=mid+1;
 19         else
 20             r=mid-1;
 21     }
 22     return num[r];
 23 }
 24 
 25 void update(int i)
 26 {
 27     if(!tree[i])
 28         return ;
 29     tree[i+i]=tree[i+i+1]=tree[i];
 30     tree[i]=0;
 31 }
 32 void change(int tl,int tr,int l,int r,int i,int co)
 33 {
 34     if(tl>r||tr<l) return ;
 35     if(tl<=l&&r<=tr)
 36     {
 37         tree[i]=co;
 38         return ;
 39     }
 40     update(i);
 41     int mid=(l+r)/2;
 42     change(tl,tr,l,mid,i+i,co);
 43     change(tl,tr,mid+1,r,i+i+1,co);
 44 }
 45 int require(int l,int r,int i)
 46 {
 47     int mid=(l+r)/2;
 48     if(tree[i])
 49     {
 50         if(!tab[tree[i]])
 51         {
 52             tab[tree[i]]=1;
 53             return 1;
 54         }
 55         return 0;
 56     }
 57     if(l==r)
 58         return 0;
 59     return require(l,mid,i+i)+require(mid+1,r,i+i+1);
 60 }
 61 void init()
 62 {
 63     scanf("%d",&n);
 64     for(int i=1; i<=n; i++)
 65     {
 66         scanf("%d%d",l+i,r+i);
 67         x[i*3-2]=l[i];x[i*3-1]=r[i];x[i*3]=(l[i]+r[i])/2;
 68     }
 69     sort(x+1,x+3*n+1);
 70     memset(num,0,sizeof(num));
 71     for(int i=1; i<=3*n; i++)
 72     {
 73         num[i]=num[i-1];
 74         if(x[i]!=x[i-1]) num[i]++;
 75     }
 76     for(int i=1; i<=n; i++)
 77     {
 78         l[i]=binary_search1(l[i]);
 79         r[i]=binary_search1(r[i]);
 80     }
 81 }
 82 
 83 void solve()
 84 {
 85     memset(tree,0,sizeof(tree));
 86     for(int i=1; i<=n; i++)
 87     {
 88         change(l[i],r[i],1,3*n,1,i);
 89     }
 90     memset(tab,0,sizeof(tab));
 91     int ans=require(1,3*n,1);
 92     printf("%d
",ans);
 93 }
 94 
 95 int main()
 96 {
 97     scanf("%d",&c);
 98     while(c--)
 99     {
100         init();
101         solve();
102     }
103     return 0;
104 }
View Code