题目描述
Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。
张贴规则如下：
electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；
所有张贴的海报的高度必须与electoral墙的高度一致的；
每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；
后贴的海报可以覆盖前面已贴的海报或部分海报。
现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。
输入输出格式
输入格式：
第一行： N M 分别表示electoral墙的长度和海报个数
接下来M行: Ai Bi 表示每张海报张贴的位置
输出格式：
输出贴完所有海报后，在electoral墙上还可以看见的海报数。
这题其实挺不错的，很典型的那种区间染色问题，所以记录一下，以便日后复习。
解法一：线段树
这种题一看就是线段树，我们选择边判断边建树，这样就省去了build和pushdown。把线段树用来存储每条线段是否全部露出来，判断的时候，如果目标线段里有一个点没有被挡住（即segtree[root]==0），那么这条海报就会露出来，ans++，然后把整条线段染色后上推，由于我们刚刚对线段树储存元素的要求，所以上推法则就是：如果一个点有一个子树有标记，那么它也有标记。记得从最上面那个海报开始判断，这样应该就没什么问题了。
#include<cstdio>
#include<iostream>
using namespace std;
int flag,sum[],i,m,n;
int a[],b[],ans;
inline void pushup(int rt){
sum[rt]=sum[rt<<]&&sum[rt<<|];
}
inline void cck(int rt,int l,int r,int x,int y){
if (sum[rt]) return;
if (x>r||y<l) return;
if (x<=l&&r<=y){
flag=; sum[rt]=;
return;
}
int mid=(l+r)>>;
if (mid>=x) cck(rt<<,l,mid,x,y);
if (mid<r) cck(rt<<|,mid+,r,x,y);
pushup(rt);
}
int main(){
scanf("%d%d",&m,&n);
m=;
for (i=; i<=n; i++){
scanf("%d%d",&a[i],&b[i]);
m=max(m,b[i]);
}
for (i=n; i>=; i--){
flag=;
cck(,,m,a[i],b[i]);
if (flag) ans++;
}
printf("%d",ans);
return ;
}
解法二：浮水法
这是一种专门解决区间染色问题的方法，思路大概是这样：
还是倒着判断，找到与海报i相交的海报j，不管他们的公共部分（因为被j挡住了），之后判断它们不相交的部分（这时i的面积变成了公共部分的面积，可能有两个公共部分，这里由递归实现），方法详见代码注释。
inline void water(int l,int r,int now,int p){ //p就是i，now用来枚举j，l,r是当前判断i的边界，a是左边界，b是右边界
if (vis[p]) return; //vis用于快速推出递归
while (now<=n&&(l>=b[now]||r<=a[now])) now++; //这里是判断相交
if (now>n){ //now>n则没有海报挡得住i了
ans++; vis[p]=;
return;
}
if (l<a[now]&&r>a[now]) water(l,a[now],now+,p); //不好讲，要不，自己画个图模拟一下？
if (r>b[now]&&l<b[now]) water(b[now],r,now+,p); //同上？
}完整代码
#include<cstdio>
#include<iostream>
using namespace std;
int vis[],a[],b[];
int ans,n,m,i;
inline void water(int l,int r,int now,int p){
if (vis[p]) return;
while (now<=n&&(l>=b[now]||r<=a[now])) now++;
if (now>n){
ans++; vis[p]=;
return;
}
if (l<a[now]&&r>a[now]) water(l,a[now],now+,p);
if (r>b[now]&&l<b[now]) water(b[now],r,now+,p);
}
int main(){
scanf("%d%d",&m,&n);
for (i=; i<=n; i++){
scanf("%d%d",&a[i],&b[i]);
b[i]++;
}
vis[n]=; ans=;
for (i=n-; i>=; i--){
water(a[i],b[i],i+,i);
}
printf("%d",ans);
return ;
}