Count Color
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 32217 | Accepted: 9681 |
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
思路:线段树,每个节点记录是否当前区间只被一种颜色覆盖,如果是就将此颜色记录下来,如果不是,说明不是单色区间,那么就继续寻找其子区间,直到找到单色区间为止。其实很简单,因为整个区间必定是由一个个单色区间组成的!!!
一开始这题提交的时候超时了,很费解,后来我把全局变量mid改成局部变量居然过了,不知道为什么,难道CPU对这两者的访问效率不同?反正很费解。。。,以后注意吧,少用全局变量。
AC 代码:
1 #include<stdio.h> 2 #include<string.h> 3 #define L(x) (x << 1) 4 #define R(x) (x << 1|1) 5 #define MAX 100000 6 #define T 40 7 typedef struct 8 { 9 int l,r; 10 int cover; 11 }Node; 12 Node node[3*MAX]; 13 int color[T]; 14 int sum; 15 void build(int l,int r,int k) 16 { 17 node[k].l = l; 18 node[k].r = r; 19 if(l == r) 20 return ; 21 int mid = (l+r) >> 1; 22 build(l,mid,L(k)); 23 build(mid+1,r,R(k)); 24 } 25 26 void insert(int l,int r,int clr,int k) 27 { 28 if(l <= node[k].l && r >= node[k].r) 29 { 30 node[k].cover = clr; 31 return ; 32 } 33 else 34 { 35 if(node[k].cover > 0) 36 { 37 node[L(k)].cover = node[k].cover; 38 node[R(k)].cover = node[k].cover; 39 node[k].cover = 0; 40 } 41 if(l > node[L(k)].r) 42 insert(l,r,clr,R(k)); 43 else if(r <= node[L(k)].r) 44 insert(l,r,clr,L(k)); 45 else 46 { 47 insert(l,node[L(k)].r,clr,L(k)); 48 insert(node[R(k)].l,r,clr,R(k)); 49 } 50 } 51 } 52 53 void get_result(int l,int r,int k) 54 { 55 if(node[k].cover > 0) 56 { 57 color[node[k].cover] = 1; 58 } 59 else 60 { 61 if(l > node[L(k)].r) 62 get_result(l,r,R(k)); 63 else if(r <= node[L(k)].r ) 64 get_result(l,r,L(k)); 65 else 66 { 67 get_result(l,node[L(k)].r,L(k)); 68 get_result(node[R(k)].l,r,R(k)); 69 } 70 } 71 } 72 73 int main() 74 { 75 int n,t,m,i,j; 76 int a,b,c,d,e; 77 char str[5]; 78 //freopen("in.c","r",stdin); 79 while(~scanf("%d%d%d",&n,&t,&m)) 80 { 81 memset(str,0,sizeof(str)); 82 memset(color,0,sizeof(color)); 83 build(1,n,1); 84 node[1].cover = 1; 85 for(i = 1;i <= m;i ++) 86 { 87 scanf("%s",str); 88 if(!strcmp(str,"C")) 89 { 90 scanf("%d%d%d",&a,&b,&c); 91 d = a < b?a:b; 92 e = a > b?a:b; 93 insert(d,e,c,1); 94 } 95 if(!strcmp(str,"P")) 96 { 97 sum = 0; 98 scanf("%d%d",&a,&b); 99 memset(color,0,sizeof(color)); 100 d = a < b?a:b; 101 e = a > b?a:b; 102 get_result(d,e,1); 103 for(j = 1;j <= t;j ++) 104 { 105 if(color[j]) 106 sum ++; 107 } 108 printf("%d ",sum); 109 } 110 memset(str,0,sizeof(str)); 111 } 112 } 113 return 0; 114 }