Time Limit: 2 Seconds Memory Limit: 65536 KB
Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.
Your task is counting the segments of different colors you can see at last.
Input
The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
x1 x2 c
x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.
All the numbers are in the range [0, 8000], and they are all integers.
Input may contain several data set, process to the end of file.
Output
Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.
If some color can't be seen, you shouldn't print it.
Print a blank line after every dataset.
Sample Input
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1
Sample Output
1 1
2 1
3 1
1 1
0 2
1 1
题意:
有N(1到8000)种颜色,给出N行a,b,c,表示a到b这个区间填充c颜色,N次输入的颜色可以覆盖前面的颜色,最后输出能看见的颜色中,一共有几段(颜色要按从小到大输出)。
思路:
用线段树延迟标记。
AC:
#include<cstdio> #include<string.h> #include<map> #define MAX (8000+5) #define INT 10000 using namespace std; typedef struct { int l; //左边界 int r; //右边界 int co; //颜色域 int ad; //标记域 }node; node no[MAX*3]; int col[MAX],from[MAX],to[MAX]; int fin[MAX]; //fin用来保存这条线段最后的颜色 void build(int from,int to,int i) { int mid=(from+to)/2; no[i].l=from; no[i].r=to; no[i].ad=-1; no[i].co=-1; if(to-from==1) return; build(from,mid,2*i); build(mid,to,2*i+1); } void add(int from,int to,int i,int c) { int mid=(no[i].l+no[i].r)/2; if(from==no[i].l&&to==no[i].r) { no[i].ad=c; return; } else { if(no[i].ad!=-1) { no[i].co=no[i].ad; no[2*i].ad=no[i].ad; no[2*i+1].ad=no[i].ad; no[i].ad=-1; } if(from>=mid) add(from,to,2*i+1,c); if(to<=mid) add(from,to,2*i,c); if(from<mid&&to>mid) { add(from,mid,2*i,c); add(mid,to,2*i+1,c); } } } void find(int i) { int mid=(no[i].l+no[i].r)/2; if(no[i].r-no[i].l==1) { if(no[i].ad!=-1) no[i].co=no[i].ad; fin[no[i].l]=no[i].co; } else { if(no[i].ad!=-1) { no[i].co=no[i].ad; no[2*i].ad=no[i].ad; no[2*i+1].ad=no[i].ad; no[i].ad=-1; } find(2*i); find(2*i+1); } } int main() { int n; while(scanf("%d",&n)!=EOF) { int ma=-1,mi=INT; memset(fin,-1,sizeof(fin)); for(int i=1;i<=n;i++) { scanf("%d%d%d",&from[i],&to[i],&col[i]); if(from[i]<mi) mi=from[i]; if(to[i]>ma) ma=to[i]; } //建树 build(mi,ma,1); //添加颜色 for(int i=1;i<=n;i++) add(from[i],to[i],1,col[i]); //查找颜色段 find(1); //用map关联容器存储最后结果 map<int,int> m; m.clear(); for(int i=mi;i<=ma-1;i++) { if(fin[i]==-1) continue; if(i==mi&&fin[mi]!=-1) m[fin[i]]++; if(i>mi&&fin[i]!=fin[i-1]) m[fin[i]]++; } //输出结果 map<int,int>::iterator it; for(it=m.begin();it!=m.end();it++) printf("%d %d\n",it->first,it->second); printf("\n"); } return 0; }
总结:
1.线段树的区间要想清楚如何分法;
2.查询完后,想清楚要如何判断有几段;
相关推荐
zoj 1610 Count the Colors.md
定义线段树的数据结构 struct Line{ int left, right, count; Line *leftChild, *rightChild; Line(int l, int r): left(l), right(r) {} };
Count the frequency distribution of units digits
How to count the number of lines in a text file
Matlab codes for analyzing the size distribution of nanoparticles
android-count-the-days android project in kotlin to count the days from a time point. MIT licensed. I needed an app that would count days since a date and days until. The current apps on the market, ...
labview labview_labview示例之Count the Number
In The Irrationals, the first popular and comprehensive book on the subject, Julian Havil tells the story of irrational numbers and the mathematicians who have tackled their challenges, from ...
cone low in matlab for count MATLAB program to calculate the size of the law of the conical tank A time of emptying the tank
进入中断判断到低电平,低电平判断 一直累加 Count_Lead++,累积低电平的采集时间,判断到高电平,就判断此时 Count_Lead 的值是否在 70 跟 200之间。(备注:5.6ms/80us=70 16ms/80us=200)。 ③ 引导头通过进入数据...
Count = 0 Count = 0 Count = 0 While count < 100: While count < 100: While count ! pramming is fun! pramming is fun! Count += 1 Count += 1 Count += 1 #B #B #B #C #C #C 答: 答: 答:A A A 处一直为 处
Count the number of attributes specified by the application. All attributes appear in pairs, except the terminating None.
count++; if(count==60) { count=0; mc++; } } /*LCD1602数据修改部分,如果哪里需要,就在那个函数里修改 不必再这里修改,同时不要出现两处同时修改,数据会被覆盖的*/ void LCD1602_Allot() { ...
layui laypage插件如何通过ajax返回动态count值,然后重置laypage count值
Ot is used to detect red pixels an image. And count the pixel
shell script file to count the number of girls who have filled the questionnaire
count the number of set hits for this segment.
Add an environment variable. Count the number of existing ones, and then allocate up a new vector of environment strings and add ours to it.
To count total file in the current directory