데이터 구조 - 선분 트 리 - 구간 색칠 문제
16702 단어 데이터 구조
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
선분 나무의 전형 적 인 응용
코드:
1 #include "cstdio" //zju 1610
2 #include "cstring"
3 #include "iostream"
4 using namespace std;
5
6 #define N 8005
7 const int NoColor = -1; //
8 const int MulColor = -2; //
9
10 struct node
11 {
12 int l,r;
13 int col;
14 }Tree[4*N];
15
16 int a[N],many[N]; //a[] ,many[]
17
18 void Build(int t,int l,int r) //
19 {
20 Tree[t].l = l;
21 Tree[t].r = r;
22 Tree[t].col = NoColor; //
23 if(Tree[t].l+1==Tree[t].r)
24 return ;
25 int mid = (Tree[t].l + Tree[t].r)/2;
26 Build(t<<1,l,mid);
27 Build(t<<1|1,mid,r);
28 }
29
30 void Update(int t,int l,int r,int k)
31 {
32 if(Tree[t].col == k) // ,
33 return ;
34 if(Tree[t].l==l && Tree[t].r==r) // , ,return ;
35 { Tree[t].col = k; return ; }
36 if(Tree[t].l+1==Tree[t].r) // , ,return ;
37 { Tree[t].col = k; return ; }
38 if(Tree[t].col != MulColor) // , ;
39 {
40 Tree[t<<1].col = Tree[t].col;
41 Tree[t<<1|1].col = Tree[t].col;
42 }
43 Tree[t].col = MulColor; //
44 int mid = (Tree[t].l+Tree[t].r)/2;
45 if(r<=mid)
46 Update(t<<1,l,r,k);
47 else if(l>=mid)
48 Update(t<<1|1,l,r,k);
49 else
50 {
51 Update(t<<1,l,mid,k);
52 Update(t<<1|1,mid,r,k);
53 }
54 }
55
56 void Stats(int t) //
57 {
58 int i,j;
59 if(Tree[t].l+1==Tree[t].r)
60 {
61 a[Tree[t].l] = Tree[t].col;
62 return ;
63 }
64 if(Tree[t].col>=0)
65 {
66 for(i=Tree[t].l; i<Tree[t].r; ++i)
67 a[i] = Tree[t].col;
68 return ;
69 }
70 Stats(t<<1);
71 Stats(t<<1|1);
72 }
73
74 int main()
75 {
76 int n;
77 int i,j;
78 int x,y,k;
79 while(scanf("%d",&n)!=-1)
80 {
81 Build(1,1,N); //
82 while(n--)
83 {
84 scanf("%d %d %d",&x,&y,&k);
85 x++; y++;
86 Update(1,x,y,k); // ,
87 }
88 memset(a,0,sizeof(a));
89 memset(many,0,sizeof(many));
90 Stats(1);
91 int t = -1;
92
93 for(i=1; i<=8000; ++i)
94 {
95 if(a[i]==t) continue;
96 t = a[i];
97 if(t!=-1)
98 many[t]++;
99 }
100 for(i=0; i<=8000; ++i)
101 {
102 if(many[i])
103 printf("%d %d
",i,many[i]);
104 }
105 printf("
");
106 }
107 return 0;
108 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.