# 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

``````
#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;

scanf("%s", ops);
if(ops == '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 == '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;
}

``````