POJ2528市长的海报Posters

来历

POJ2528

题目

【题意】
n(n<=10000)个人依次贴海报,
给出每张海报所贴的范围li,ri(1<=li<=ri<=10000000)。
求出最后还能看见多少张海报。(注意:没多组数据)
【输入样例】
5
1 4
2 6
8 10
3 4
7 10
【输出样例】
4

分析

关于离散化,可以参考这里

推荐一个好的算法,但我没有这么做:
如果更新次数太多的话,可以考虑从后往前更新
即如果更新时发现之前已经有一张海报完全覆盖他了
就可以不用更新(因为没有必要)
这样的算法时间会减少很多

代码

不完整,通用部分可以参考这里

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
struct DisNod
{
int x,p,z;
}a[20010],b[20010];
void Discretization(int n)//离散化
{
for(int i=1;i<=n;i+=2)
{
scanf("%d %d",&a[i].x,&a[i+1].x);a[i+1].x++;
a[i].p=i;a[i+1].p=i+1;
b[i]=a[i];b[i+1]=a[i+1]; //拷贝
}
sort2(1,n);//排序
b[1].z=1;
for(int i=2;i<=n;i++)
{
if(b[i].x==b[i-1].x) b[i].z=b[i-1].z;
else b[i].z=b[i-1].z+1;
a[b[i].p].z=b[i].z;
}
}
struct Manager
{
int l,r,tl,tr,c;
bool lazy;
}f[40010];
void update(int x)
{
f[x].lazy=false;
if(f[x].tl>0 and f[x].tr>0)
{
int tl=f[x].tl,tr=f[x].tr;
f[tl].lazy=f[tr].lazy=true;
f[tl].c=f[tr].c=f[x].c;
}
}
void change(int now,int l,int r,int c)
{
if(l==f[now].l and r==f[now].r)
{
f[now].c=c;
f[now].lazy=true;
return;
}
if(f[now].lazy) update(now);
……
}
int num=0;
int build(int l,int r)
{
……
f[x].lazy=false;
……
}
char ch[5];bool v[20010]={0};
int main()
{
scanf("%d",&n);n*=2;
Discretization(n);
build(1,b[n].z);
for(int i=1;i<=n;i+=2)
change(1,a[i].z,a[i+1].z,i);
int s=0;
for(int i=1;i<=num;i++)
{
if(f[i].lazy) update(i);
if(!f[i].tl and !v[f[i].c])
v[f[i].c]=1,s++;
}
printf("%d",s);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/96fc.html
转载请注明出处,谢谢!