poj 2528 Mayor's posters (线段树+染色)-白红宇

poj 2528 Mayor's posters (线段树+染色)

阅读量：4652 次

发布时间：2019-06-09

本文共 970 字，大约阅读时间需要 3 分钟。

题目大意：

在一个长度为1e7单位的板子上贴海报，后贴上的会覆盖原来贴上的，问最后能看到几个海报（露出部分也可以）

思路

因为板子是1e7，但给出的海报个数为1e4，所以考虑离散化，普通的离散化是会漏掉颜色，比如 1 3 1 10 1 4 7 10，所以要在长度大于1区间之间在加一个点，记录这个区间的颜色。然后就是col本身即使树，也可以把他当lazy自身向下传递，最后查询时只需要查询有几种颜色，如果有颜色直接返回即可。

在updata时注意不要让叶子节点向下传递.....

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #define mem(a,b) memset(a,b,sizeof(a))const int maxn=4e4+10;using namespace std;struct node{ int l,r;}e[maxn];int arr[maxn],col[4*maxn],vis[maxn],n;int ans=0;void init(){ mem(col,0); mem(vis,0); mem(arr,0); mem(e,0); ans=0;}void updata(int l,int r,int left,int right,int c,int now){ int mid=(l+r)/2; if(left<=l&&r<=right) { col[now]=c; return ; } if(l>right) return ; if(r
            
             1;i--)//加点 { if(arr[i]-arr[i-1]!=1) arr[++m]=arr[i-1]+1; } sort(arr+1,arr+1+m);// for(int i=1;i<=m;i++)// {// cout<
             
              <<" ";// }cout<