首页 > 其他 > 详细

P3740 [HAOI2014]贴海报

时间:2019-02-20 18:15:55      阅读:168      评论:0      收藏:0      [点我收藏+]

题目描述

Bytetown城市要进行市长竞选,所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理,城市委员会为选民准备了一个张贴海报的electoral墙。

张贴规则如下:

  1. electoral墙是一个长度为N个单位的长方形,每个单位记为一个格子;

  2. 所有张贴的海报的高度必须与electoral墙的高度一致的;

  3. 每张海报以“A B”表示,即从第A个格子到第B个格子张贴海报;

  4. 后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断,张贴完所有海报后,在electoral墙上还可以看见多少张海报。

输入输出格式

输入格式:

第一行: N M 分别表示electoral墙的长度和海报个数

接下来M行: Ai Bi 表示每张海报张贴的位置

输出格式:

输出贴完所有海报后,在electoral墙上还可以看见的海报数。

代码

线段树模版题,求区间覆盖问题,注意从后往前枚举区间

核心在于pushup操作回溯

vis[rt]=vis[lson]&&vis[rson]

 

技术分享图片
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn=10000000+10,maxm=1000+5;
bool vis[maxn<<2];
int n,m;
int l[maxm],r[maxm];
int ans=0;
bool flag;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>9||ch<0){if(ch==-)f=-1;ch=getchar();}
    while(ch<=9&&ch>=0){x=(x<<3)+(x<<1)+ch-0;ch=getchar();}
    return x*f;
}
void pushup(int rt)
{
    vis[rt]=vis[lson]&&vis[rson];
}
void update(int L,int R,int l,int r,int rt)
{
    if(vis[rt])return;
    if(L<=l&&r<=R)
    {
        vis[rt]=1;
        flag=1;
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)
    update(L,R,l,m,lson);
    if(m<R)
    update(L,R,m+1,r,rson);
    pushup(rt);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    l[i]=read(),r[i]=read();
    for(int i=m;i>=1;i--)
    {
        flag=0;
        update(l[i],r[i],1,n,1);
        if(flag)ans++;
    }
    printf("%d",ans);
    return 0;
}
View Code

 

P3740 [HAOI2014]贴海报

原文:https://www.cnblogs.com/DriverBen/p/10408110.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!