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

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

Count Color

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 45268		Accepted: 13705

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:

“C A B C” Color the board from segment A to segment B with color C.
“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

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;
}