poj2528&&zoj1610线段树区间染色问题

区间点染色

poj2528
题意:n(n<=10000)个人依次贴海报,给出每张海报所贴的范围li,ri(1<=li<=ri<=10000000)。

如图
求出最后还能看见多i少张海报。

由于 l,r范围太大,先离散化处理一下.
然后对于这题可以看作对区间点的染色问题,求最后整个区间有多少种不同颜色。用线段树的区间更新,和区间查询,修改一下就可以完成,详见代码,很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
const int N=1e4+10;
int x1[N],x2[N],vis[6*N*4],cnt[N],ans,n;
int compress(int *x1,int *x2,int w){
vector<int> xs;
for(int i=1;i<=n;i++){
for(int d=-1;d<=1;d++){
int tx1=x1[i]+d,tx2=x2[i]+d;
if(1<=tx1&&tx1<=w) xs.push_back(tx1);
if(1<=tx2&&tx2<=w) xs.push_back(tx2);
}
}
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
for(int i=1;i<=n;i++){
x1[i]=find(xs.begin(),xs.end(),x1[i])-xs.begin()+1;
x2[i]=find(xs.begin(),xs.end(),x2[i])-xs.begin()+1;
}
return xs.size();
}
void push_down(int rt){
if(vis[rt]){
vis[rt<<1]=vis[rt<<1|1]=vis[rt];
vis[rt]=0;
}
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){
vis[rt]=c;
return;
}
int m=(l+r)>>1;
push_down(rt);
if(L<=m) update(L,R,c,l,m,rt<<1);
if(R>m) update(L,R,c,m+1,r,rt<<1|1);
}
void query(int l,int r,int rt){
if(l==r){
if(vis[rt]>0&&!cnt[vis[rt]]){
ans++;cnt[vis[rt]]=1;
}
return;
}
push_down(rt);//lazy操作,向下传递
int m=l+r>>1;
query(l,m,rt<<1);
query(m+1,r,rt<<1|1);
}
int main(){
int T;scanf("%d",&T);
while(T--){
int w=0;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",x1+i,x2+i);
}
w=compress(x1,x2,1e7);
memset(cnt,0,sizeof(cnt));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
update(x1[i],x2[i],i,1,w,1);
}
ans=0;
query(1,w,1);
printf("%d\n",ans);
}
}

区间线段染色

zoj1610
题意:
0~8000长的线段,有n个染色操作,每次染[a,b]区间(重点:染线段,不是染点),问最后被覆盖的颜色有多少个,他们各有几个区间段?
思路:这题注意是对线段染色,而不是对点染色。
例如:
经过以下两个操作
1 2 1
3 4 1

1 2 和3 4之间都是1颜色而2 3 直接并没有染上颜色,所以还是看成两段1颜色,而不是一段。
那这个问题怎么解决呢?
这里有一个技巧:对于每次区间染色[a,b]
我是染色[a+1,b]区间,这样就可以解决区间线段染色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int N=1e4;
int vis[N<<2],col[N],last;
void push_down(int rt){
if(vis[rt]>=0){
vis[rt<<1]=vis[rt<<1|1]=vis[rt];
vis[rt]=-1;
}
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){
vis[rt]=c;
return;
}
int m=(l+r)>>1;
push_down(rt);
if(L<=m) update(L,R,c,l,m,rt<<1);
if(R>m) update(L,R,c,m+1,r,rt<<1|1);
}
void query(int l,int r,int rt){
if(l==r){
if(vis[rt]!=-1&&last!=vis[rt]) col[vis[rt]]++;
last=vis[rt];
return;
}
push_down(rt);
int m=l+r>>1;
query(l,m,rt<<1);
query(m+1,r,rt<<1|1);
}
int main(){
int n;
while(~scanf("%d",&n)){
memset(vis,-1,sizeof(vis));
memset(col,0,sizeof(col));
for(int i=0;i<n;i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
if(a+1<=b) update(a+1,b,c,1,8000,1);
}
last=-1;
query(1,8000,1);
for(int i=0;i<=8000;i++){
if(col[i]>0) printf("%d %d\n",i,col[i]);
}
printf("\n");
}
}
扫码也许会变得更强~!