Description
Your task is counting the segments of different colors you can see at last.
Input
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
If some color can‘t be seen, you shouldn‘t print it.
Print a blank line after every dataset.
Sample Input
Sample Output
1 1
0 2
1 1
/*AC代码*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int maxn=50000;
int col[maxn*4];
int Hash[maxn*2];
int tmp[maxn*2];
int k;
void PushDown(int rt){
if(col[rt]>=0){
col[rt*2]=col[rt];
col[rt*2+1]=col[rt];
col[rt]=-1;
}
}
void update(int rt,int L,int R,int l_ran,int r_ran,int _col){
if(l_ran<=L&&R<=r_ran){
col[rt]=_col;
return ;
}
PushDown(rt);
if(l_ran<=mid){
update(lson,l_ran,r_ran,_col);
}
if(r_ran>mid){
update(rson,l_ran,r_ran,_col);
}
}
void query(int rt,int L,int R){
if(col[rt]>=0){
for(int i=L;i<=R;i++){ //区别在这里
tmp[i]=col[rt];
} //区别在这里
col[rt]=-1;
return ;
}
if(L==R)
return ;
query(lson);
query(rson);
}
void get_ans(int n){
if(tmp[0]>=0)
Hash[tmp[0]]=1;
for(int i=1;i<n;i++){
if(tmp[i]!=tmp[i-1]){
Hash[tmp[i]]++;
}
}
}
void debug2(){
for(int i=0;i<k;i++){
printf("..%d %d\n",i,tmp[i]);
}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF ){
int ta,tb,tc;
memset(tmp,-1,sizeof(tmp));
memset(col,-1,sizeof(col));
for(int i=0;i<n;i++){
scanf("%d%d%d",&ta,&tb,&tc);
update(1,0,maxn,ta*2,tb*2,tc);
}
memset(Hash,0,sizeof(Hash));
k=0;
query(1,0,maxn);
// printf("%d\n",k);
// debug2();
// get_ans(k);
for(int i=0;i<maxn;i++){ //区别在这里
if(tmp[i]!=-1){
int j;
for( j=i;j<maxn&&tmp[i]==tmp[j];j++);
Hash[tmp[i]]++;
i=j-1;
}
} //区别在这里
for(int i=0;i<maxn+20;i++){
if(Hash[i]){
printf("%d %d\n",i,Hash[i]);
}
} printf("\n");
}
return 0;
}
/*WA代码*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int maxn=50000;
int col[maxn*4];
int Hash[maxn*2];
int tmp[maxn*2];
int k=0;
void PushDown(int rt){
if(col[rt]>=0){
col[rt*2]=col[rt];
col[rt*2+1]=col[rt];
col[rt]=-1;
}
}
void update(int rt,int L,int R,int l_ran,int r_ran,int _col){
if(l_ran<=L&&R<=r_ran){
col[rt]=_col;
return ;
}
PushDown(rt);
if(l_ran<=mid){
update(lson,l_ran,r_ran,_col);
}
if(r_ran>mid){
update(rson,l_ran,r_ran,_col);
}
}
void query(int rt,int L,int R){
if(col[rt]>=0){
tmp[k++]=col[rt]; //区别在这里
col[rt]=-1;
return ;
}
if(L==R)
return ;
query(lson);
query(rson);
}
void get_ans(int n){
if(tmp[0]>=0)
Hash[tmp[0]]=1;
for(int i=1;i<n;i++){
if(tmp[i]!=tmp[i-1]){
Hash[tmp[i]]++;
}
}
}
void debug2(){
for(int i=0;i<k;i++){
printf("..%d %d\n",i,tmp[i]);
}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF ){
int ta,tb,tc;
memset(col,-1,sizeof(col));
for(int i=0;i<n;i++){
scanf("%d%d%d",&ta,&tb,&tc);
update(1,0,maxn,ta*2,tb*2,tc);
}
memset(Hash,0,sizeof(Hash));
k=0;
query(1,0,maxn);
// printf("%d\n",k);
// debug2();
get_ans(k); //区别在这里
for(int i=0;i<maxn+20;i++){
if(Hash[i]){
printf("%d %d\n",i,Hash[i]);
}
} printf("\n");
}
return 0;
}
ZOJ 1610——Count the Colors——————【线段树区间替换、求不同颜色区间段数】
原文：http://www.cnblogs.com/chengsheng/p/4395625.html