主题素材传送门,来自国家地理杂志水墨歌唱家James L.

1969年7月美国加州的一群芭蕾舞者,来自国家地理杂志摄影师James L.
AmosBallet dancers in colorful costume practice a scene in The
Nutcracker in San Diego, California, July 1969.Tips on using color in
your photographs.PHOTOGRAPH BY JAMES L. AMOS, NATIONAL GEOGRAPHICMAR. 31
2013 #DANCE #主题素材传送门,来自国家地理杂志水墨歌唱家James L.。1960’S #NATGEO #VINTAGE #PHOTOGRAPHY 1,213 NOTES

题目传送门:

 

Count Color

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 45259   Accepted: 13703

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

线段树对区间操作,简单题
给你一段L长的线让你染色,有T中颜色,共有O次命令,
命令分为
C:给x到y染成c色
P:看x到y一共有多少种颜色

  1 #include<stdio.h>
  2 #include<string.h>
  3 int cc[1000];
  4 struct A{
  5     int l,r,c;
  6 }t[100000*4+4];
  7 void bulid(int p,int l,int r)
  8 {
  9     t[p].l=l;t[p].r=r;t[p].c=1;
 10     if(l==r)
 11         return ;
 12         int mid=(t[p].l+t[p].r)>>1;
 13     bulid(p*2,l,mid);
 14     bulid(p*2+1,mid+1,r);
 15 }
 16 void cha(int l,int r,int c,int p)
 17 {
 18     if(t[p].l==l&&t[p].r==r)
 19     {
 20         t[p].c=c;
 21         return ;
 22     }
 23     if(t[p].c==c)
 24         return ;
 25     if(t[p].c!=-1)
 26     {
 27         t[p*2].c=t[p].c;
 28         t[p*2+1].c=t[p].c;
 29         t[p].c=-1;
 30         
 31     }int mid=(t[p].l+t[p].r)>>1;
 32         if(r<=mid)
 33         {
 34             cha(l,r,c,p*2);
 35         }
 36         else if(l>mid)
 37         {
 38             cha(l,r,c,p*2+1);
 39         }
 40         else 
 41         {
 42             cha(l,mid,c,p*2);
 43             cha(mid+1,r,c,p*2+1);
 44         }
 45 }
 46 void se(int l,int r,int p)
 47 {
 48     if(t[p].c!=-1)
 49     {
 50         cc[t[p].c]=1;
 51     //    printf("!%dn",t[p].c);
 52         return ;
 53     }
 54     int mid=(t[p].l+t[p].r)>>1;
 55         if(r<=mid)
 56         {
 57             se(l,r,p*2);
 58         }
 59         else if(l>mid)
 60         {
 61             se(l,r,p*2+1);
 62         }
 63         else 
 64         {
 65             se(l,mid,p*2);
 66             se(mid+1,r,p*2+1);
 67             
 68         }
 69 }
 70 int main()
 71 {
 72     int l,t,o,i,j,a,b,c;
 73     char aa;
 74     while(scanf("%d%d%d",&l,&t,&o)!=EOF)
 75     {
 76     bulid(1,1,l);
 77         while(o--)
 78         {
 79             getchar();
 80         aa=getchar();
 81         
 82         if(aa=='C')
 83         {
 84             scanf("%d%d%d",&a,&b,&c);
 85             if(a>b)
 86             {
 87                 a=a^b;
 88                 b=a^b;
 89                 a=a^b;    
 90             }    
 91             cha(a,b,c,1);
 92         }
 93         else if(aa=='P')
 94         {
 95             scanf("%d%d",&a,&b);
 96             if(a>b)
 97             {
 98                 a=a^b;
 99                 b=a^b;
100                 a=a^b;    
101             }
102             memset(cc,0,sizeof(cc));
103             se(a,b,1);
104             int sun=0;
105             for(j=1;j<=t;j++)
106             {
107                 if(cc[j]==1)
108                     sun++;
109             }
110                 
111                 printf("%dn",sun);
112                 
113         }
114         }
115         
116         
117     }
118     return 0;    
119 }

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图