POJ 2528.Mayor's posters-线段树(成段替换、离散数据、简单hash）

POJ2528.Mayor's posters

这道题真的是线段数的经典的题目，因为数据很大，直接建树的话肯定不可以，所以需要将数据处理一下，没有接触离散化的时候感觉离散化这个东西相当高级，其实在不知道离散化是什么东西之前，就已经用过这种东西了，只是不知道叫什么。关于离散化，就是根据数的相对大小对他们进行映射，用小的数来表示他们。所以要先排序，然后去重，然后操作就可以。有排序版的离散化和STL版的离散化(自己起的名字。。。)，代码里写的是排序版的，就是for循环遍历的时候，和身边的数比较一下是否是相同的数，然后操作。具体的不介绍，自行百度吧。

这道题就是贴海报，只与两个边界值有关系，但是如果两个数中间的间隔大于1的话，中间应该加数，否则新的点覆盖到上面的时候，就会出错。举个例子，假设我点为1,2,7,10，我离散化映射为0,1,2,3，区间操作为(1,10),(1,2),(7,10),因为线段树是对点进行维护，所以是对点染色，对点染色的话，就将两个点都改变了，所以1,2,7,10都变了颜色，只能看到2种，但是正确的应该是3种，(2,7)还能看到，所以需要在间隔大于1的时候中间加点，这样就不会出错了。映射的时候二分查找就会快很多，其他的就没什么了。

代码:

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<cstdlib>

 #include<queue>

 #include<map>

 #include<stack>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 const int inf=0x3f3f3f3f;

 const double eps=1e-;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 int col[maxn<<],hash[maxn<<],a[maxn],li[maxn],ri[maxn],cnt;

 void pushdown(int rt)

 {

     if(col[rt]!=-){

         col[rt<<]=col[rt<<|]=col[rt];

         col[rt]=-;

     }

 }

 void update(int L,int R,int c,int l,int r,int rt)

 {

     if(L<=l&&r<=R){

         col[rt]=c;

         return ;

     }

     pushdown(rt);

     int m=(l+r)>>;

     if(L<=m) update(L,R,c,lson);

     if(R> m) update(L,R,c,rson);

 }

 void query(int l,int r,int rt)

 {

     if(col[rt]!=-){

         if(hash[col[rt]]==) cnt++;

         hash[col[rt]]=;

         return ;

     }

     if(l==r) return ;

     int m=(l+r)>>;

     query(lson);

     query(rson);

 }

 int reflect(int key,int n,int a[])

 {

     int l=,r=n-;

     while(l<=r){

         int m=(l+r)>>;

         if(a[m]==key) return m;

         if(a[m]< key) l=m+;

         else r=m-;

     }

     return -;

 }

 int main()

 {

     int t,n;

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         int h=,k=;

         memset(col,-,sizeof(col));

         memset(hash,,sizeof(hash));

         for(int i=;i<n;i++){

             scanf("%d%d",&li[i],&ri[i]);

             a[h++]=li[i];a[h++]=ri[i];

         }

         sort(a,a+h);

         for(int i=;i<h;i++){

             if(a[i]!=a[i-]) a[k++]=a[i];

         }

         for(int i=k-;i>;i--){

             if(a[i]!=a[i-]+) a[k++]=a[i]+;

         }

         sort(a,a+k);

         for(int i=;i<n;i++){

             int l=reflect(li[i],k,a);

             int r=reflect(ri[i],k,a);

             update(l,r,i,,k,);

         }

         cnt=;

         query(,k,);

         printf("%d\n",cnt);

     }

     return ;

 }

巴特西

POJ 2528.Mayor's posters-线段树(成段替换、离散数据、简单hash）

最新文章

热门文章