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
题意：
在一条长度为8000的线段上染色，每次把区间[a,b]染成c颜色。显然，后面染上去的颜色会覆盖掉之前的颜色。
求染完之后，每个颜色在线段上有多少个间断的区间。
用区间更新的方式，对于区间内的先不更新，当出现新的线段覆盖的时候在pushdown，mark[]遍历一下离根最近的color不为-1（为染色）的就行了，最后通过sum统计出从到大的就好了。
C++版本一
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
const int N = 8000+10;
using namespace std;
int t,n,q;
//long long tree[N<<2];
int lazy[N<<2];
int a[N];
int b[N];
void PushDown(int rt){
if(lazy[rt]){
lazy[rt*2] = lazy[rt];
lazy[rt*2+1] = lazy[rt];
lazy[rt] = 0;
}
}
void EndBuild(int l,int r,int rt){
// l,r 代表的是这个区间内的左端点 和 右端点， rt代表的是 [l,r] 这个区间内的值是存在哪一个位置的。
if(l==r){
b[l]=lazy[rt];
return ;
}
int m=(l+r)/2;// 对于区间区分，我们一般将m点划入左半边区间
PushDown(rt);
EndBuild(l,m,rt*2);
EndBuild(m+1,r,rt*2+1);
//PushUp(rt); // PushUp 函数是通过2个子节点来更新现在这个节点的状态， 对于不同的要求需要不同的写法。
}
void Updata(int l,int r,int rt,int L,int R,int C){// l,r,rt 与前面的定义一样， L代表的是要更新区间的位置，C代表的是修改后的值
if(L <= l && r <= R){// 这里不能写成 if(l == L) 因为有可能左端点恰好是要更新的位置， 但是还有右端点， 我们直接更新的只有区间 [L,L]。
lazy[rt] = C;
return ;
}
int m=(l+r)/2;
PushDown(rt);
if(L<=m) Updata(l,m,rt*2,L,R,C);//要更新的区间在左边部分，所以往左边走，更新左边
if(m < R) Updata(m+1,r,rt*2+1,L,R,C);//要更新的区间在右边部分， 往右边走，更新右边
}
void init(){
//memset(tree,0,sizeof(tree));
memset(lazy,0,sizeof(lazy));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
}
int main()
{
while(scanf("%d",&n)!=EOF){
init();
//StartBuild(1,8001,1);
int x1,x2,c;
while(n--){
scanf("%d%d%d",&x1,&x2,&c);
Updata(1,8001,1,x1+1,x2,c+1);
}
EndBuild(1,8001,1);
for(int i=1;i<N-1;i++){
if(b[i]!=b[i+1])
a[b[i]]++;
}
for(int i=1;i<N;i++){
if(a[i]>0)
cout << i-1 <<" " << a[i] << endl;
}
cout << endl;
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
//线段树区间更新
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define INF 0x3f3f3f3f
#define MAX 8010
#define LL long long
using namespace std;
struct Tree
{
int l,r;
int color;
};
Tree tree[MAX*4];
void pushdown(LL x) ///用于更新color数组
{
LL tmp = x<<1 ;
tree[tmp].color = tree[x].color; ///由子节点通过增加
tree[tmp+1].color = tree[x].color;
tree[x].color=-1;
}
void build(int l,int r,int x)
{
tree[x].l=l , tree[x].r=r , tree[x].color=-1;
if(l==r) return ;
int tmp=x<<1;
int mid=(l+r)>>1;
build(l,mid,tmp);
build(mid+1,r,tmp+1);
}
void update(int l,int r,int c,int x) ///分别表示区间的左 ， 右 ， 增加的值 ，当前父亲节点
{
if(r<tree[x].l||l>tree[x].r) return ;
if(l<=tree[x].l&&r>=tree[x].r) ///该区间为需要更新区间的子区间
{
tree[x].color = c;
return ;
}
if(tree[x].color!=-1) pushdown(x); ///更新从上向下更新color
update(l,r,c,x<<1);
update(l,r,c,(x<<1)+1);
}
int mark[MAX<<2],coun=0; ///注意大小
void query(int l ,int r ,int x )
{
if((l==tree[x].l&&r==tree[x].r && tree[x].color!=-1) || tree[x].l == tree[x].r){
mark[coun++] = tree[x].color; ///要计算的区间包括了该区间
return ;
}
LL tmp=x<<1;
LL mid=(tree[x].l+tree[x].r)>>1;
if(r<=mid) return query(l,r,tmp);
else if(l>mid) return query(l,r,tmp+1);
else{
query(l,mid,tmp) ;
query(mid+1,r,tmp+1);
}
}
int main()
{
int x1[MAX<<2],x2[MAX<<2],c[MAX<<2];
int sum[MAX<<2];
int mmax=-1,m;
while(~scanf("%d",&m))
{
coun = 0;
mmax=-1;
memset(mark,-1,sizeof(mark));
memset(sum,0,sizeof(sum));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&x1[i],&x2[i],&c[i]);
if(mmax<x1[i]) mmax = x1[i];
if(mmax<x2[i]) mmax = x2[i];
}
build(1,mmax,1);
for( int i = 0;i<m; i++ ){
if(x1[i]+1>x2[i]) continue;
update(x1[i]+1,x2[i],c[i],1); ///这个地方需要加1，减1因为线段树是从1开始的所以表示单位没有0，因此不好处理
}
if(mmax<0) continue;
query(1,mmax,1);
for(int i=0;i<coun;){ ///注意统计的方式，下面的while不能少
if(mark[i]==-1){i++ ;continue;}
int x = mark[i];
while(x == mark[++i] && i<coun);
sum[x]++;
}
for(int i=0;i<8010;i++)
if(sum[i])
printf("%d %d\n",i,sum[i]);
printf("\n");
}
return 0;
}
C++版本三
题目大意：
在一条长度为8000的线段上染色，每次把区间[a,b]染成c颜色。显然，后面染上去的颜色会覆盖掉之前的颜色。
求染完之后，每个颜色在线段上有多少个间断的区间。
分析与总结：
这题是成段更新lazy标记的题，并不算难，但是因为一些原因一直让我过不去。。。
1. 昨天做了这题，但是一直连样例都出不来 = =～！早上起来，突然醒悟发现了问题所在，题目每次给的染色段是把[a,b]染成c，之前一直以为就是把a～b的所有点都染成c， 其实不是这样的，要染色的不是点，而是区间，例如要染[0,1]，并不是把0，1两点染色，而是把[0,1]这一个单位区间进行染色。 假设有一个样例：
1 2 1
3 4 1
那么这个样例应该输出1 2. 只需要在纸上画一下就可以发现，区间【2，3】是没有被染色的，所以有两个间断的区间颜色是1。
解决这个问题的办法是，建立线段树build(1,1,8000)，代表区间1～8000， 然后更新时是update(1,1,8000, a+1,b,c);
2. 由于没有仔细看题目，看错了一个地方，于是一直RE（在zoj上叫做Segmentation Fault）：
The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.
这句话的意思是只有n条线段被染色，而我一直理解成了是在一条n个单位区间长度的线段上染色 = =～ 于是就悲剧了。
正解是这句话：All the numbers are in the range [0, 8000], and they are all integers.
#include<iostream>
#include<cstdio>
#include<cstring>
#define mem(str,x) memset(str,(x),sizeof(str))
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
#define FF(i,n) for(int i=0; i<(n); ++i)
#define mid ((left+right)>>1)
#define len (right-left+1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
#define STOP puts("Stop Here~");
using namespace std;
const int MAXN = 8005;
int n,col[MAXN<<2],vis[MAXN<<2],ans[MAXN<<2];
inline void push_down(int rt){
if(col[rt] != -1){
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
}
void update(int rt,int left,int right,int l,int r,int data){
if(l<=left && right<=r){
col[rt] = data;
return;
}
if(col[rt] == data) return;
if(col[rt]!=-1)push_down(rt);
int m = mid;
if(l <= m)update(lson,l,r,data);
if(r > m)update(rson,l,r,data);
}
void query(int rt,int left,int right){
if(col[rt]>=0){
for(int i=left; i<=right; ++i)
vis[i] = col[rt];
return;
}
if(left!=right && col[rt] == -1){
int m = mid;
query(lson);
query(rson);
}
}
int main(){
int a,b,c;
while(~scanf("%d",&n)){
memset(col,-1,sizeof(col));
for(int i=0; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
if(a>=b)continue;
update(1,1,8000,a+1,b,c);
}
mem(vis,-1);
query(1,1,8000);
int i = 1;
mem(ans,0);
while(i<MAXN){
int color=vis[i], j=i+1;
if(color==-1){++i; continue;}
while(vis[j]!=-1 && vis[j]==color && j<MAXN) ++j;
++ans[color];
i=j;
}
for(int i=0; i<MAXN; ++i)if(ans[i])
printf("%d %d\n",i,ans[i]);
puts("");
}
return 0;
}
京公网安备 11010502036488号