Count Color
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 46856 | Accepted: 14193 |
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.
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
题解：
线段树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 233333;
int sum[33];
struct qer
{
int l, r;
int col;
}tree[maxn*4];
void build(int p, int l, int r)
{
tree[p].l = l;
tree[p].r = r;
tree[p].col = 1;
if (l == r)
return ;
int mid = (l+r) >> 1;
build (p<<1, l, mid);
build (p<<1|1, mid+1, r);
}
void change(int p, int l, int r, int m)
{
if (tree[p].col == m)
return ;
if (tree[p].l == l && tree[p].r == r)
{
tree[p].col = m;
return ;
}
if (tree[p].col != -1)
{
tree[p<<1].col = tree[p<<1|1].col = tree[p].col;
tree[p].col = -1;
}
int mid = (tree[p].l + tree[p].r)>>1;
if (l > mid)
change(p<<1|1, l, r, m);
else if (r <= mid)
change(p<<1, l, r, m);
else
{
change(p<<1, l, mid, m);
change(p<<1|1, mid+1, r, m);
}
}
void ask(int p, int l, int r)
{
if (tree[p].col != -1)
{
sum[tree[p].col] = 1;
return ;
}
else
{
int mid = (tree[p].l+tree[p].r)>>1;
if (l > mid)
ask(p<<1|1, l, r);
else if (r <= mid)
ask(p<<1, l, r);
else
{
ask(p<<1, l, mid);
ask(p<<1|1, mid+1, r);
}
}
}
int main()
{
int L, T, O;
int a, b, c;
while (scanf("%d%d%d", &L, &T, &O)!=EOF)
{
build (1, 1, L);
while (O--)
{
char s;
getchar();
scanf("%c", &s);
if (s == 'C')
{
scanf("%d%d%d", &a, &b, &c);
change(1, a, b, c);
}
int ans = 0;
if (s == 'P')
{
memset(sum, 0, sizeof(sum));
scanf("%d%d", &a, &b);
ask(1, a, b);
for (int i = 1; i <= T; i++)
if (sum[i])
ans++;
printf("%d\n", ans);
}
}
}
return 0;
}