poj - 2777

Posted by WildCow on February 2, 2018

Count Color

Time Limit: 1000MS
Memory Limit: 65536K

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


会给我们木棍的长度,颜料的种类以及操作数,木棍的初始颜色全是1号颜色,每次操作选定棍子上的一个范围使其全部涂上一种颜色,最后问操作结束后,棍子上有多少种不同的颜色

唔很明显的线段树。。。然后颜色最多30种,考虑每种颜色用二进制表示,二进制的1的个数表示颜色的种类的个数,这样对于单个的颜色x,用来表示则是 1 « (x - 1),然后延迟标记lazy表示该节点的儿子都会被染成lazy色(类似于区间更新(唔我好像还没写区间更新))。同时感谢hls让我对lazy有了更深的理解。

最后每个节点的颜色种类数等于子节点进行位或运算。最后相当于对全区间进行一次查询。

本质上其实还是一个裸题,但开始还是被窝写坏惹。。。。


#include <cstdio>
#include <iostream>  
#include <algorithm>  
#include <cstring>  
using namespace std;  
  
const int N = 100010;  
  
struct Tree  
{  
    int l;  
    int r;  
    int v;  
    int lazy;  
};  
  
int n, m, w;  
Tree tree[N * 4];  
  
void up(int x)  
{  
    tree[x].v = tree[x << 1].v | tree[x << 1 | 1].v;  
}  
  
void down(int x)  
{  
    int t = tree[x].lazy;  
  
    if(t){  
        tree[x << 1].v = t;  
        tree[x << 1].lazy = t;  
        tree[x << 1 | 1].v = t;  
        tree[x << 1 | 1].lazy = t;  
        tree[x].lazy = 0;  
    }  
}  
  
void build(int x, int l, int r)  
{  
    tree[x].l = l;  
    tree[x].r = r;  
    tree[x].v = 1;  
    tree[x].lazy = 0;  
  
    if(l == r){  
        tree[x].v = 1 << 0;  
        tree[x].lazy = 0;  
    }  
    else{  
        int mid = l + ((r - l) >> 1);  
  
        build(x << 1, l, mid);  
        build(x << 1 | 1, mid + 1, r);  
        up(x);  
    }  
}  
  
void update(int x, int l, int r, int v)  
{  
    int ll = tree[x].l;  
    int rr = tree[x].r;  
  
    if(ll == l && rr == r){  
        tree[x].v = 1 << (v - 1);  
        tree[x].lazy = 1 << (v - 1);  
    }  
    else{  
        int mid = ll + ((rr - ll) >> 1);  
  
        down(x);  
        if(l <= mid){  
            update(x << 1, l, min(mid, r), v);  
        }  
        if(mid < r){  
            update(x << 1 | 1, max(mid + 1, l), r, v);  
        }  
        up(x);  
    }  
}  
  
int query(int x, int l, int r)  
{  
    int ll = tree[x].l;  
    int rr = tree[x].r;  
  
    if(ll == l && rr == r){  
        return tree[x].v;  
    }  
    else{  
        int mid = ll + ((rr - ll) >> 1);  
        int ans = 0;  
  
        down(x);  
        if(l <= mid){  
            ans = ans | query(x << 1, l ,min(mid, r));  
        }  
        if(r > mid){  
            ans = ans | query(x << 1 | 1, max(l, mid + 1), r);  
        }  
        up(x);  
  
        return ans;  
    }  
}  
  
int main(int argc, char const *argv[])  
{  
    int t;  
  
    while(scanf("%d%d%d", &n, &m, &w) == 3){  
        build(1, 1, n);  
  
  
        for(int i = 0; i < w; i ++){  
            char ops[40];  
  
            scanf("%s", ops);  
            if(ops[0] == 'C'){  
                int l, r, v;  
  
                scanf("%d%d%d", &l, &r, &v);  
                if(r < l){  
                    swap(l, r);  
                }  
                update(1, l, r, v);  
            }  
            else if(ops[0] == 'P'){  
                int l, r;  
                int t;  
                int ans = 0;  
  
                scanf("%d%d", &l, &r);  
                if(r < l){  
                    swap(l, r);  
                }  
                t = query(1, l, r);  
                for(int j = 0; j < m; j ++){  
                    if(t & (1 << j)){  
                        ans ++;  
                    }  
                }  
                printf("%d\n", ans);  
            }  
  
  
        }  
    }  
  
  
    return 0;  
}