线段树成段更新 poj 2528 Mayor's posters

题目大意：在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报

思路：离散化+线段树成段更新+hash

普通离散化有缺陷，所以我们在排序后的数组上加一些处理，比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
线段树功能:update:成段替换 query:简单hash

代码如下：

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<algorithm>
  4 using namespace std;
  5 #define lson l,m,rt<<1
  6 #define rson m+1,r,rt<<1|1
  7 #define N 20010
  8 int tree[N<<4],li[N],ri[N],hash[N<<2],tmp[N<<2];
  9 int ans;
 10 int bin(int x,int n)
 11 {
 12     int low=0,high=n-1;
 13     while(low<=high)
 14     {
 15         int mid=(low+high)>>1;
 16         if(tmp[mid]==x)
 17             return mid;
 18         else if(tmp[mid]<x)
 19             low=mid+1;
 20         else
 21             high=mid-1;
 22     }
 23     return -1;
 24 }
 25 void pushdown(int rt)
 26 {
 27     if(tree[rt]!=-1)
 28     {
 29         tree[rt<<1]=tree[rt<<1|1]=tree[rt];
 30         tree[rt]=-1;
 31     }
 32 }
 33 void update(int L,int R,int c,int l,int r,int rt)
 34 {
 35     if(L<=l&&R>=r)
 36     {
 37         tree[rt]=c;
 38         return ;
 39     }
 40     pushdown(rt);
 41     int m=(l+r)>>1;
 42     if(L<=m)
 43         update(L,R,c,lson);
 44     if(R>m)
 45         update(L,R,c,rson);
 46 }
 47 void query(int l,int r,int rt)
 48 {
 49     if(tree[rt]!=-1)
 50     {
 51         if(!hash[tree[rt]])
 52         {
 53             ans++;
 54             hash[tree[rt]]=1;
 55         }
 56         return ;
 57     }
 58     if(l==r)
 59         return ;
 60     int m=(l+r)>>1;
 61     query(lson);
 62     query(rson);
 63 }
 64 int main()
 65 {
 66     int t,i,j,n;
 67     scanf("%d",&t);
 68     while(t--)
 69     {
 70         scanf("%d",&n);
 71         int k=0;
 72         for(i=0;i<n;i++)
 73         {
 74             scanf("%d%d",&li[i],&ri[i]);
 75             tmp[k++]=li[i];
 76             tmp[k++]=ri[i];
 77         }
 78         sort(tmp,tmp+k);
 79         int m=1;
 80         for(i=1;i<k;i++)
 81             if(tmp[i]!=tmp[i-1])
 82                 tmp[m++]=tmp[i];
 83         for(i=m-1;i>0;i--)
 84             if(tmp[i]!=tmp[i-1]+1)
 85                 tmp[m++]=tmp[i-1]+1;
 86         sort(tmp,tmp+m);
 87         memset(tree,-1,sizeof(tree));
 88         for(i=0;i<n;i++)
 89         {
 90             int a=bin(li[i],m);
 91             int b=bin(ri[i],m);
 92             update(a,b,i,0,m,1);
 93         }
 94         memset(hash,0,sizeof(hash));
 95         ans=0;
 96         query(0,m,1);
 97         printf("%d\n",ans);
 98     }
 99     return 0;
100 }

View Code