ZOJ1610 Count the Colors (分块写法) 区间覆盖-白红宇

ZOJ1610 Count the Colors (分块写法) 区间覆盖

阅读量：220 次

发布时间：2019-03-01

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

为了解决这个问题，我们需要计算在一条直线上最终可见的不同颜色的线段数量。线段可能会被后面的线段覆盖，因此我们需要高效地处理这些覆盖关系。

方法思路

我们使用分块处理方法来解决这个问题。分块处理通过将问题划分为多个块，每个块内部处理，然后合并结果。这种方法在处理大规模数据时非常有效。

分块划分：预先将线段划分为多个块，每个块的大小大约为√n。这样可以减少递归深度并提高效率。

懒标记处理：使用懒标记来记录区间覆盖情况，避免频繁更新带来的性能问题。

线段更新：对于每个线段，更新对应的块，标记颜色。

块合并：在处理完所有线段后，遍历每个块，合并标记，找出可见的颜色数量。

统计颜色：统计每个颜色的可见段数，并输出结果。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;int maxm = 8001;int block = sqrt(maxm);int num = (maxm + block - 1) / block;int l[num + 1], r[num + 1];int a[maxm + 1], belong[maxm + 1];int mark[num + 1];void reset(int node) { if (mark[node] != -1) { for (int i = l[node]; i <= r[node]; ++i) { a[i] = mark[node]; } mark[node] = -1; }}void check(int node, int val) { for (int i = l[node]; i <= r[node]; ++i) { if (a[i] != val) { mark[node] = -1; return; } } mark[node] = val;}void update(int x, int y, int val) { int current = belong[x]; if (l[current] > r[y]) { return; } reset(current); for (int i = x; i <= y; ++i) { a[i] = val; } check(current, val); if (x < l[current] || y > r[current]) { return; } int left = belong[l[current]]; int right = belong[r[current]]; if (x < l[left] || y > r[right]) { return; } reset(left); for (int i = x; i <= y; ++i) { a[i] = val; } check(left, val); reset(right); for (int i = l[right]; i <= y; ++i) { a[i] = val; } check(right, val); for (int i = belong[x] + 1; i <= belong[y]; ++i) { if (mark[i] != -1) { mark[i] = val; } }}void build() { int ma = maxm; l[1] = 1; r[1] = block; for (int i = 2; i <= num; ++i) { l[i] = r[i - 1] + 1; r[i] = r[i - 1] + block; } r[num] = ma; for (int i = 1; i <= ma; ++i) { belong[i] = (i - 1) / block + 1; }}int main() { while (true) { int n; scanf("%d", &n); if (n == 0) { break; } build(); for (int i = 1; i <= n; ++i) { int x, y, c; scanf("%d %d %d", &x, &y, &c); update(x, y, c); } vector
                  
                    color_count(10000, 0); for (int i = 1; i <= maxm; ++i) { if (a[i] != -1) { color_count[a[i]]++; } } for (int i = 1; i <= maxm; ++i) { if (color_count[i] > 0) { printf("%d %d\n", i, color_count[i]); } } printf("\n"); }}

代码解释

分块划分：预处理分块结构，确定每个点属于哪个块。

懒标记处理：使用标记数组记录覆盖情况，避免频繁更新。

线段更新：对于每个线段，更新对应的块，标记颜色。

块合并：在处理完所有线段后，合并每个块的标记，计算可见颜色的数量。

统计颜色：统计每个颜色的可见段数，并输出结果。

这种方法通过分块处理和懒标记，高效地解决了线段覆盖问题，确保了算法的性能和正确性。

转载地址：http://rxuv.baihongyu.com/

你可能感兴趣的文章

Objective-C实现fibonacci search斐波那契查找算法(附完整源码)