POJ 2777-Count Color（线段树-区间染色查询）

爱被打了一巴掌 2022-06-17 03:12 181阅读 0赞

Count Color

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;45268</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;13705</td> 
  </tr> 
 </tbody> 
</table>

Description

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.  
  
There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:  
  
1. "C A B C" Color the board from segment A to segment B with color C.  
2. "P A B" Output the number of different colors painted between segment A and segment B (including).  
  
In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output

Ouput results of the output operation in order, each line contains a number.

Sample Input

2 2 4
    C 1 1 2
    P 1 2
    C 2 2 2
    P 1 2

Sample Output

2
    1

Source

[POJ Monthly--2006.03.26][],dodo

## 题目意思： ##

L长的木板染上T种颜色，有O个操作，其中C a b c表示a~b长度区间全部染成c这种颜色，Q a b表示查询区间a~b内不同颜色的个数。

## 解题思路： ##

线段树节点存储该区间内的颜色，单点区间肯定就是染成的颜色，大区间如果标记为-1则表示该区间由多种颜色的小区间组成，注意初始情况下木板均为同一种颜色，可以记为1。

一共有最多30种颜色，所以用bool vis\[30\]数组标记，在每次查询的时候清空，查询到点或区间颜色相同时，对该颜色标记为true，最后统计1~T这T种颜色使用的个数即vis是true的情况。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 275000
    bool vis[50];//1表示该区间有该颜色
    int ans[MAXN*4];
    struct Node //树
    {
        int l,r;//左右节点
        int col;//区间内的颜色
    };
    Node tree[MAXN*5];
    
    void BuildTree(int root, int l, int r)//建树
    {
        tree[root].l=l;
        tree[root].r=r;
        tree[root].col=1;//初始状态都是同一种颜色
        if(l!=r)
        {
            BuildTree(2*root,l,(l+r)/2);
            BuildTree(2*root+1,(l+r)/2+1,r);
        }
    }
    void Insert(int i,int l,int r,int c)//插入
    {
        if(tree[i].col==c)//同色
            return ;
        if(tree[i].l==l&&tree[i].r==r)
        {
            tree[i].col=c;//染色
            return ;
        }
        if(tree[i].col!=-1)//同色
        {
            tree[2*i].col=tree[2*i+1].col=tree[i].col;
            tree[i].col=-1;
        }
        int mid=(tree[i].l+tree[i].r)/2;
        if(r<=mid)
            Insert(2*i,l,r,c);
        else if(l>mid)
            Insert(2*i+1,l,r,c);
        else
        {
            Insert(2*i,l,mid,c);
            Insert(2*i+1,mid+1,r,c);
        }
    }
    void Query(int i,int l,int r)
    {
        if(tree[i].col!=-1)//同色
        {
            vis[tree[i].col]=true;
            return;
        }
        int mid=(tree[i].l+tree[i].r)/2;
        if(r<=mid)
            Query(2*i,l,r);
        else if(l>mid)
            Query(2*i+1,l,r);
        else
        {
            Query(2*i,l,mid);
            Query(2*i+1,mid+1,r);
        }
    }
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int l,t,n;
        scanf("%d%d%d\n",&l,&t,&n);
        //while(~scanf("%d%d%d\n",&l,&t,&n))
        {
            BuildTree(1,1,n);//建树
            while(n--)
            {
                char ch;
                cin>>ch;
                if(ch=='C')
                {
                    int a,b,c;
                    scanf("%d%d%d",&a,&b,&c);
                    if(a>b) swap(a,b);//如果a>b
                    Insert(1,a,b,c);
                }
                else if(ch=='P')
                {
                    memset(vis,false,sizeof(vis));
                    int a,b,ans=0;
                    scanf("%d%d",&a,&b);
                    if(a>b) swap(a,b);
                    Query(1,a,b);
                    for(int i=1; i<=t; ++i)
                        if(vis[i]) ++ans;
                    printf("%d\n",ans);
                }
            }
        }
        return 0;
    }

[POJ Monthly--2006.03.26]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2006.03.26