Mayor’s posters
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 90347 Accepted: 25793
Description
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
Every candidate can place exactly one poster on the wall.
All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
The wall is divided into segments and the width of each segment is one byte.
Each poster must completely cover a contiguous number of wall segments.
They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters’ size, their place and order of placement on the electoral wall.
Input
The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,… , ri.
Output
For each input data set print the number of visible posters after all the posters are placed.
The picture below illustrates the case of the sample input.
Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4
题目大意：
有n张海报(1<=n<=10000)，每张海报宽为wi(1<=wi<=10000000)，然后现在给你n张海报，并且按照先后顺序贴在一面墙宽为10000000上，如果当前海报和上一张海报宽度相同，就会覆盖掉上一张海报，最后问你这面墙上还有多少张海报可以看见。
思路：
先吐槽一波，做了一天，一开始先是疯狂re，原来是宽度太大，建不了树所以re了，然后离散化解决了。
解决完re后又疯狂wa，送了poj一面红，wa的人都懵了，最后无奈之下只能和别人代码检查一下，找出两个wa点了，wa1：我更新完左右儿子节点，忘记回带更新父节点了。wa2：我是先判断左右儿子是否可以被覆盖，被覆盖就return，没覆盖就递归，但是这个逻辑是错的，因为我一上来就考虑左右儿子节点而没有考虑当前节点，假设当前节点是父节点并且全部覆盖，那还有必要去左右儿子吗？显示不需要了。
吐槽完了说一下思路：
因为它是对区间做更新操作和查询操作，所以我们可以想到用数组和线段树去模拟，用数组的话修改查询时间复杂度都是O(n)肯定t了，所以我们考虑一下线段树。
因为最多有n张海报，n取最大值有10000，根据二叉树的性质可以算出2^(i-1)>=10000，i=15，也就是说这颗二叉树最多有15层，然后算一下最多总共有 2 ^15-1=32767，也就是说我们需要开这么大的数组。（建议开4倍空间），然后因为1<=li<=ri<=10000000，然后用这个范围做线段树的话，想都不要想肯定不行，所以我们需要离散化一下，不懂离散化可以看一下这里https://blog.csdn.net/qq_43553133/article/details/88797565。
离散化完了后我们逆序更新树，因为最后贴上去的海报肯定能被看见，只有每次更新能够找到一个没被覆盖的范围（或者节点？）ans++，最后更新完就是我们要的答案了。
两份代码
代码1（wa）:
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1<<21;
struct node{
ll x,y;
};
struct node node[maxn];
struct segment{
ll l,r;
ll v;
};
struct segment Node[maxn];
ll t[maxn];
ll ans=0;bool flag=0;
void build(ll i,ll l,ll r){
Node[i].l=l;
Node[i].r=r;
Node[i].v=0;
if(l==r)return ;
ll mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
void update(ll i,ll l,ll r){
if(Node[i].l==l&&Node[i].r==r){
if(Node[i<<1].v>0&&Node[i<<1|1].v>0)return;
Node[i].v=1;flag=1;
return;
}
ll mid=(Node[i].l+Node[i].r)>>1;
if(r<=mid){
if(Node[i<<1].v>0)return;
update(i<<1,l,r);
}else if(l>mid){
if(Node[i<<1|1].v>0)return;
update(i<<1|1,l,r);
}else{
if(Node[i<<1].v>0)return;
update(i<<1,l,mid);
if(Node[i<<1|1].v>0)return;
update(i<<1|1,mid+1,r);
}
}
int main(){
ll T;ll n;
scanf("%lld",&T);
while(T--){
ans=0;ll cnt=1;
scanf("%lld",&n);
for(ll i=0;i<n;i++){
scanf("%lld%lld",&node[i].x,&node[i].y);
t[cnt++]=node[i].x;
t[cnt++]=node[i].y;
}
sort(t+1,t+1+n*2);
ll m=unique(t+1,t+1+n*2)-(t+1);
for(ll i=0;i<n;i++){
node[i].x=lower_bound(t+1,t+1+2*n,node[i].x)-(t);
node[i].y=lower_bound(t+1,t+1+2*n,node[i].y)-(t);
// printf("%d %d \n",node[i].x,node[i].y);
}
build(1,1,cnt);
for(ll i=n-1;i>=0;i--){
flag=0;
update(1,node[i].x,node[i].y);
if(flag)ans++;
}
printf("%lld\n",ans);
}
}
第二份（ac）：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1<<21;
struct node{
ll x,y;
};
struct node node[maxn];
struct segment{
ll l,r;
ll v;
};
struct segment Node[maxn];
ll t[maxn];
ll ans=0;bool flag=0;
void build(ll i,ll l,ll r){
Node[i].l=l;
Node[i].r=r;
Node[i].v=0;
if(l==r)return ;
ll mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
void update(ll i,ll l,ll r){
if(Node[i].v)return;
if(Node[i].l==l&&Node[i].r==r){
Node[i].v=1;flag=1;
return;
}
ll mid=(Node[i].l+Node[i].r)>>1;
if(r<=mid){
update(i<<1,l,r);
}else if(l>mid){
update(i<<1|1,l,r);
}else{
update(i<<1,l,mid);
update(i<<1|1,mid+1,r);
}
Node[i].v=Node[i<<1].v&&Node[i<<1|1].v;
}
int main(){
ll T;ll n;
scanf("%lld",&T);
while(T--){
ans=0;ll cnt=1;
scanf("%lld",&n);
for(ll i=0;i<n;i++){
scanf("%lld%lld",&node[i].x,&node[i].y);
t[cnt++]=node[i].x;
t[cnt++]=node[i].y;
}
sort(t+1,t+1+n*2);
ll m=unique(t+1,t+1+n*2)-(t+1);
for(ll i=0;i<n;i++){
node[i].x=lower_bound(t+1,t+1+2*n,node[i].x)-(t);
node[i].y=lower_bound(t+1,t+1+2*n,node[i].y)-(t);
// printf("%d %d \n",node[i].x,node[i].y);
}
build(1,1,2*n);
for(ll i=n-1;i>=0;i--){
flag=0;
update(1,node[i].x,node[i].y);
if(flag)ans++;
}
printf("%lld\n",ans);
}
}
京公网安备 11010502036488号