POJ 2528 Mayor's posters 解题报告

题意：给定你海报，覆盖区间，问你最后可以看见多少海报　　

解题思路：线段树的离散化问题，把大的数值变成小的数值，然后区间覆盖统计就行了，但是要注意不相邻的数值在离散化的时候要处理，不然会导致 1-10 1-4 6-10 这样结果变为两个海报！

解题代码：

  1 #include <stdlib.h>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #define MAXN 51000
  5 int hs[MAXN];
  6 struct step
  7 {
  8   int x, y ;
  9 }steps[MAXN];
 10 int qu[MAXN];
 11 struct node
 12 {
 13   int left ,right ,mid;
 14   int cover;
 15 }tree[MAXN*6];
 16 struct hst
 17 {
 18   int num,value;
 19   struct hst * next ;
 20 }hstp[MAXN];
 21 struct hst *newnode()
 22 {
 23   struct hst *p;
 24   p = (hst*)malloc(sizeof(hst));
 25   p->next = NULL;
 26   p->num = 0;
 27   p->value = 0 ;
 28   return p;
 29 }
 30 void add(int temp,int value)
 31 {
 32    int t = temp % 10007;
 33    hstp[t].num ++;
 34    struct hst *p = newnode();
 35    p->num = temp;
 36    p->value = value;
 37    p->next = hstp[t].next;
 38    hstp[t].next = p ;
 39 }
 40 int  fin(int temp)
 41 {
 42    int t = temp % 10007;
 43    struct hst *p = &hstp[t];
 44    for(int i = 1;i <= hstp[t].num; i ++)
 45    {
 46     p = p ->next ;
 47     if(p->num == temp)
 48       return p->value;
 49    }
 50 
 51 }
 52 
 53 int cmp(const void *a, const void *b)
 54 {
 55   return *(int *)a - *(int *)b;
 56 }
 57 int L(int c)
 58 {
 59   return c * 2 ;
 60 }
 61 int R(int c)
 62 {
 63   return c * 2 + 1;
 64 }
 65 void build(int c, int p , int v)
 66 {
 67   tree[c].left = p ;
 68   tree[c].right = v;
 69   tree[c].mid = (p + v)/2;
 70   tree[c].cover = 0 ;
 71   if(p == v)
 72     return ;
 73   build(L(c),p,tree[c].mid);
 74   build(R(c),tree[c].mid +1 ,v );
 75 }
 76 void update(int c, int p , int v ,int value)
 77 {
 78      if(p <= tree[c].left && v >= tree[c].right)
 79      {
 80          tree[c].cover = value;
 81          return;
 82      }
 83      if(tree[c].cover != 0)
 84      {
 85        tree[L(c)].cover = tree[c].cover;
 86        tree[R(c)].cover = tree[c].cover;
 87        tree[c].cover = 0 ;
 88      }
 89      if(v <= tree[c].mid) update(L(c),p,v,value);
 90      else if(p > tree[c].mid) update(R(c),p,v,value);
 91      else
 92      {
 93        update(L(c),p,tree[c].mid,value);
 94        update(R(c),tree[c].mid+1,v,value );
 95      }
 96 }
 97 void geths(int c)
 98 {
 99    if(tree[c].left == tree[c].right || tree[c].cover != 0)
100    {
101     //  printf("%d %d %d
",tree[c].left,tree[c].right,tree[c].cover);
102       hs[tree[c].cover] = 1;
103       return ;
104    }
105     geths(L(c));
106     geths(R(c));
107 }
108 
109 int main()
110 {
111   int t;
112   scanf("%d",&t);
113   while(t--)
114   {
115     memset(hstp,0,sizeof(hstp));
116     memset(hs,0,sizeof(hs));
117     memset(qu,0,sizeof(qu));
118     memset(tree,0,sizeof(tree));
119     int n;
120     scanf("%d",&n);
121     int qulen = 0 ;
122     for(int i =1 ;i <= n;i ++)
123     {
124        scanf("%d %d",&steps[i].x,&steps[i].y);
125        qulen++;
126        qu[qulen] = steps[i].x;
127        qulen++;
128        qu[qulen] = steps[i].y;
129     }
130     qsort(qu+1,qulen,sizeof(int),cmp);
131     int qutemp = 0;
132     for(int i = 1;i <= qulen;i ++)
133     {
134       if(qu[i] - qu[i-1] == 0)
135         continue;
136       else if(qu[i] - qu[i-1] != 1)
137       {
138         qutemp += 2;
139         add(qu[i],qutemp);
140       }
141       else
142       {
143          qutemp ++;
144          add(qu[i],qutemp);
145       }
146 
147 
148     }
149     build(1,1,qutemp);
150     for(int i =1 ;i <= n;i ++)
151     {
152       int a,b;
153       a = fin(steps[i].x);
154       b = fin(steps[i].y);
155     //  printf("%d %d
",a,b);
156       update(1,a,b,i);
157     }
158     int sum = 0 ;
159     geths(1);
160    for(int i= 1;i  <= n;i ++)
161    {
162      if(hs[i] != 0 )
163         sum ++;
164    }
165    printf("%d
",sum);
166 
167   }
168   return 0 ;
169 }

View Code

ps：在这题的时候还是没有深入思考离散化的弊端！！

没有梦想，何谈远方