POJ 2528 Mayor's posters（线段树染色问题+离散化）

题意：

给出一面无限长的墙，现在往墙上依次贴海报，问最后还能看见多少张海报。

题意：
这道题目就相当于对x轴染色，然后计算出最后还能看见多少种颜色。

由于数据量是给定的，所以需要进行离散化。但是这道题目的话，不能简单的离散化，前后相差大于1的话需要额外的插一个数。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,int> pll;
 15 const int INF = 0x3f3f3f3f;
 16 const int maxn = 10000 + 5;
 17 
 18 int n;
 19 int ans;
 20 int col[maxn<<4];
 21 int vis[maxn<<4];
 22 int l_pos[maxn<<2],r_pos[maxn<<2];
 23 int x[maxn<<4];
 24 
 25 void PushDown(int o)
 26 {
 27     if(col[o]!=-1)
 28     {
 29         col[o<<1]=col[o<<1|1]=col[o];
 30         col[o]=-1;
 31     }
 32 }
 33 
 34 void update(int L, int R, int l, int r, int ID, int o)
 35 {
 36     if(L<=l && R>=r)
 37     {
 38         col[o]=ID;
 39         return;
 40     }
 41     PushDown(o);
 42     int mid=(l+r)/2;
 43     if(L<=mid)  update(L,R,l,mid,ID,o<<1);
 44     if(R>mid)   update(L,R,mid+1,r,ID,o<<1|1);
 45 }
 46 
 47 void query(int L, int R, int l, int r, int o)
 48 {
 49     if(col[o]!=-1)
 50     {
 51         if(vis[col[o]]==0)  //每种颜色统计一次
 52         {
 53             ans++;
 54             vis[col[o]]=1;
 55         }
 56         col[o]=-1;
 57         return;
 58     }
 59     if(l==r)  return;
 60     PushDown(o);
 61     int mid=(l+r)/2;
 62     if(L<=mid)  query(L,R,l,mid,o<<1);
 63     if(R>mid)   query(L,R,mid+1,r,o<<1|1);
 64 }
 65 
 66 int main()
 67 {
 68     //freopen("in.txt","r",stdin);
 69     int T;
 70     scanf("%d",&T);
 71     while(T--)
 72     {
 73         memset(col,-1,sizeof(col));
 74         memset(vis,0,sizeof(vis));
 75 
 76         scanf("%d",&n);
 77         int cnt=0;
 78         for(int i=1;i<=n;i++)
 79         {
 80             scanf("%d%d",&l_pos[i],&r_pos[i]);
 81             x[++cnt]=l_pos[i];
 82             x[++cnt]=r_pos[i];
 83         }
 84 
 85         sort(x+1,x+cnt+1);
 86         int cntt=cnt;
 87         for(int i=2;i<=cntt;i++)
 88         {
 89             if(x[i]-x[i-1]>1)   x[++cnt]=x[i-1]+1;  //插点
 90         }
 91         //离散化
 92         sort(x+1,x+cnt+1);
 93         int num=unique(x+1,x+cnt+1)-(x+1);
 94         for(int i=1;i<=n;i++)
 95         {
 96             l_pos[i]=lower_bound(x+1,x+num+1,l_pos[i])-(x+1);
 97             r_pos[i]=lower_bound(x+1,x+num+1,r_pos[i])-(x+1);
 98             update(l_pos[i],r_pos[i],0,num,i,1);
 99         }
100 
101         ans=0;
102         query(0,num,0,num,1);
103         printf("%d
",ans);
104     }
105     return 0;
106 }