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

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

阅读量：220 次

发布时间：2019-03-01

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

Count the Colors

问题描述

在一条直线上画一些彩色的线段，一些以前画过的线段可能被后面的线段覆盖。

你的任务是计算你最终能看到的不同颜色的片段。

输入

每个数据集的第一行恰好包含一个整数n, 1 <= n <= 8000，等于彩色段的数量。

下面的n行每一行由3个非负整数组成，用空格隔开:

(x1, x2) c

x1和x2表示线段的左端点和右端点，c表示线段的颜色。

所有的数字都在[0,8000]范围内，它们都是整数。

输入可以包含多个数据集，处理到文件末尾。

输出

输出的每一行都应该包含一个可以从顶部看到的颜色索引，在此颜色的段数之后，应该根据颜色索引打印它们。

如果有些颜色看不到，就不应该打印出来。

在每个数据集之后打印空行。

Sample Input

0 4 4

0 3 1

3 4 2

0 2 2

0 2 3

0 1 1

3 4 1

1 3 2

1 3 1

0 1 0

1 2 1

2 3 1

1 2 0

2 3 0

1 2 1

Sample Output

1 1

2 1

3 1

1 1

0 2

1 1

分析：

线段树入门题，但是最近学了分块想拿分块写。

这题题目的n不是区间长度，区间长度是固定的8000

类似线段树laz标记。分块一样开个数组标记。记得最后重置标记！！！（pushdown）

记录下来提醒自己

我的代码（分块）：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    typedef long long ll;const int inf=0x3f3f3f3f;const int inn=0x80808080;using namespace std;const int maxm=8000+5;int n;int num,block;int mark[maxm];//其实不用开这么大的数组，但是空间不值钱int l[maxm],r[maxm];int a[maxm];int belong[maxm];void build(){ int ma=8001; memset(a,-1,sizeof a); memset(mark,-1,sizeof mark); block=sqrt(ma); num=ma/block; if(ma%block)num++; for(int i=1;i<=num;i++){ l[i]=(i-1)*block+1; r[i]=i*block; } r[num]=ma; for(int i=1;i<=ma;i++){ belong[i]=(i-1)/block+1; }}void reset(int node){ //重置标记（pushdown） if(mark[node]==-1){ return ; } 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){ if(belong[x]==belong[y]){ reset(belong[x]); for(int i=x;i<=y;i++){ a[i]=val; } check(belong[x],val); return ; } reset(belong[x]); for(int i=x;i<=r[belong[x]];i++){ a[i]=val; } check(belong[x],val); reset(belong[y]); for(int i=l[belong[y]];i<=y;i++){ a[i]=val; } check(belong[y],val); for(int i=belong[x]+1;i
                    
                     0){ printf("%d %d\n",i,ans[i]); } } printf("\n"); } return 0;}