ZOJ Problem Set - 1610

Count the Colors

---

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

---

Author: Standlove
Source: ZOJ Monthly, May 2003

乱的代码

#include
const int MAXN=;
using namespace std;
struct node{
int l,r;
int c;//color
}tree[MAXN];
int n;
int color[MAXN];
//每个节点左右端点的颜色
int leftC[MAXN];
int rightC[MAXN];

void print(){
for(int i=;i<=;i++) cout<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].c<<endl;
}

void build(int p,int l,int r){
tree[p].l=l;
tree[p].r=r;
tree[p].c=;
//拓展节点
if(l+<r){
int mid=(l+r)/;
build(*p,l,mid);
build(*p+,mid,r);
}
}

void insert(int p,int l,int r,int c){//这里的l和r代表线段的左端点和右端点
//颜色不同才有涂色的必要
if(tree[p].c!=c){
cout<<c<<endl;
int mid=(tree[p].l+tree[p].r)/;//日常拆区间
if(l==tree[p].l&&r==tree[p].r){

         tree\[p\].c=c;  
     }  
     else if(tree\[p\].l+==tree\[p\].r) return;//树的叶子节点  
     //区间不合适，我这是要拆区间的节奏，肯定会给加一种颜色造成混色  
     //可能没有交集么？？？不可能没有交集，不在左，毕在右，第一轮就给你分好了，所以肯定要进行母树颜色往下分的操作  
     else if(tree\[p\].c>=) {  
         //母树的颜色往下分  
         tree\[\*p\].c=tree\[p\].c;  
         tree\[\*p+\].c=tree\[p\].c;  
         tree\[p\].c=-;  
         if(r<mid) insert(\*p,l,r,c);  
         else if(l>mid) insert(\*p+,l,r,c);  
         else{//把线段拆了  
             insert(\*p,l,mid,c);  
             insert(\*p+,mid,r,c);  
         }  
     }

 }  

}

void count1(int p,int lc,int rc){
cout<<"p:"<=){
cout<<""<){
count1(*p,lc,tl);
count1(*p+,tr,rc);
}
//每一轮做完就看p的左右孩子是否同色或者部分同色
if(tree[*p].r==tree[*p+].l){
color[tree[p].c]--;
}
}

void count2(int p){
//单一颜色才计数
if(tree[p].c>=){
leftC[p]=tree[p].c;
rightC[p]=tree[p].c;
color[tree[p].c]++;//这种颜色的线段数加1
return;
}
else if(tree[p].r-tree[p].l>){
count2(*p);
leftC[p]=leftC[*p];
count2(*p+);
rightC[p]=rightC[*p+];
}
//每一轮做完就看p的左右孩子是否同色或者部分同色
if(rightC[*p]==leftC[*p+]){
color[rightC[*p]]--;
}
}

void printColor(){
for(int i=;i<=;i++) cout<<color[i]<<" "; cout<<endl;
}

int main(){
build(,,);
insert(,,,);
insert(,,,);
count2();
print();
printColor();
return ;
}

**题解/solution：
**

这题大体和我写的解题报告（PPT1 例2）相同，只是在统计算法上要改一下。Look down！

图，come out.            （懒得画树，将就一下）

用ls表示上一个颜色，如果当前颜色与ls不同，那给这个颜色加一。例：

ls颜色为空，而一区间为红，红加一，ls=红。   ls颜色为红，而三区间为蓝，蓝加一，ls=蓝。

以此类推……

type
arr=record
l,r:longint;
color:longint;
end;
var
tree:array [..] of arr;
ans:array [..] of longint;
n,m,ls,max_co:longint;
procedure cre(p,b,e:longint);
var
m:longint;
begin
with tree[p] do
begin
l:=b; r:=e; color:=-;
if e-b= then exit;
m:=(b+e) div ;
cre(p*,b,m);
cre(p*+,m,e);
end;
end;

procedure ins(p,a,b,c:longint);
var
m:longint;
begin
with tree[p] do
begin
if color<>c then
begin
m:=(l+r) div ;
if (a=l) and (b=r) then color:=c else
begin
if color>= then
begin
tree[p*].color:=color;
tree[p*+].color:=color;
end;
color:=-;
if b<=m then ins(p*,a,b,c) else if a>=m then ins(p*+,a,b,c) else
begin
ins(p*,a,m,c);
ins(p*+,m,b,c);
end;
end;
end;
end;
end;

procedure count(p:longint);
begin
with tree[p] do
begin
if color>= then
begin
if color<>ls then
begin
inc(ans[color]);
ls:=color;
end;
exit;
end;
if color=- then
begin
ls:=color;
exit;
end;
count(p*);
count(p*+);
end;
end;

procedure main;
var
i,x,y,z:longint;
begin
m:=;
while not eof do
begin
fillchar(ans,sizeof(ans),);
readln(n);
ls:=-; max_co:=-(maxlongint div );
cre(,,m);
for i:= to n do
begin
readln(x,y,z);
ins(,x,y,z);
if z>max_co then max_co:=z;
end;
count();
for i:= to max_co do
if ans[i]> then
writeln(i,' ',ans[i]);
writeln;
end;
end;

begin
main;
end.