POJ 2528 Mayor's posters
洛谷 UVA10587 Mayor's posters
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.
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 10Sample Output
4题目翻译：
给你一个10^7长的墙，往上面区间重复贴海报，最问贴完n张海报之后还能看见多少海报。
题解：
离散化+线段树。
因为你开10000000*4的线段树一定会MLE，所以我们这里需要引入离散化。
离散化模板抄的是大佬的。
应该是非常好用的一个模板，在此推荐给大家。
然后就是线段树了/
我在这里要着重讲一下让本蒟蒻痛苦不已的pushdown操作。
pushdown操作是线段树的精髓！！
我们假设节点now所表示的区间[L,R]，且tag[now]=id,说明now节点的整个区间都被id覆盖，就不需要再继续往它的儿子节点传递这一信息。只有当我们需要修改这个大区间的某一个子区间的时候，我们才把当前的标记下传到左右子节点，然后把当前的tag[now]清零。
这个过程请大家一定好好理解，非常重要。
最后我们需要统计答案，使用标记数组。
v[i]表示第i号海报是否被遍历过，注意，它有可能只被挡住一部分。
所以我们得出了完整思路：
输入数据，直接离散化，然后按照排好序之后的海报一张一张地开始修改，pushdown，最后依次寻找答案。
代码：
#include<cstdio>
#include<algorithm>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=200004;
int tag[maxn<<2],v[maxn<<2],ans;
void mark(int l,int r,int now,int v)
{
if(r<l) return;
tag[now]=v;
}
void pushdown(int l,int r,int now)
{
if(tag[now])
{
int mid=(l+r)>>1;
mark(l,mid,now<<1,tag[now]);
mark(mid+1,r,now<<1|1,tag[now]);
tag[now]=0;
}
}
void update(int l,int r,int now,int L,int R,int id)
{
if(l>=L&&r<=R)
{
tag[now]=id;
return;
}
pushdown(l,r,now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,now<<1,L,R,id);
if(R>mid) update(mid+1,r,now<<1|1,L,R,id);
}
void getans(int l,int r,int now)
{
if(tag[now])
{
if(v[tag[now]]==0)
{
v[tag[now]]=1, ans++;
}
return;
}
if(l==r) return;
int mid=(l+r)>>1;
if(mid>=l) getans(l,mid,now<<1);
if(r>mid) getans(mid+1,r,now<<1|1);
}
void re(int l,int r,int now)
{
v[tag[now]]=0,tag[now]=0;
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(l<=mid) re(l,mid,now<<1);
if(r>mid) re(mid+1,r,now<<1|1);
}
int c;
int A[10002<<1];
struct tree
{
int l,r,L,R;
}t[10001<<2];
int main()
{
scanf("%d",&c);
while(c--)
{
int n,cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&t[i].l,&t[i].r);
A[++cnt]=t[i].l, A[++cnt]=t[i].r;
}
sort(A+1,A+1+cnt);
for(int i=1;i<=n;++i)
{
t[i].L=lower_bound(A+1,A+1+cnt,t[i].l)-A;
t[i].R=lower_bound(A+1,A+1+cnt,t[i].r)-A;
}
for(int i=1;i<=n;i++) {
update(1,cnt,1,t[i].L,t[i].R,i);
}
getans(1,cnt,1);
printf("%d\n",ans);
ans=0;
re(1,cnt,1);
}
return 0;
}