[HAOI 2014] 포스터 붙이기.

제목 설명:

제목 분석:

제목 링크:

Ac 코드:

// luogu-judger-enable-o2
#include 
#include 
#include 
#include 
const int maxm=1e5+100; 
int tag[maxm<<2],ans[maxm],vis[maxm];
int hash[maxm*6],al[maxm],ar[maxm];
int n,m,cnt,tot;
inline void col(int o,int c){tag[o]=c;}
inline void pushdown(int o)
{
    if(tag[o]) col((o<<1),tag[o]),col((o<<1)|1,tag[o]);
    tag[o]=0;
}
void modify(int o,int l,int r,int ql,int qr,int c)
{
    if(ql<=l&&r<=qr) return (void)(col(o,c));
    pushdown(o);
    int mid=(l+r)>>1;
    if(ql<=mid) modify((o<<1),l,mid,ql,qr,c);
    if(qr>mid) modify((o<<1)|1,mid+1,r,ql,qr,c); 
}
void cover(int o,int l,int r)
{
    if(l>=r) return (void)(ans[l]=tag[o]);
    pushdown(o);
    int mid=(l+r)>>1;
    cover((o<<1),l,mid),cover((o<<1)|1,mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&al[i],&ar[i]);
        hash[++tot]=al[i],hash[++tot]=ar[i];
        hash[++tot]=al[i]-1,hash[++tot]=al[i]+1;
        hash[++tot]=ar[i]-1,hash[++tot]=ar[i]+1;
    }
    std::sort(hash+1,hash+tot+1);
    cnt=std::unique(hash+1,hash+tot+1)-hash-1;
    for(int i=1;i<=m;i++)
    {
        int ql=std::lower_bound(hash+1,hash+cnt+1,al[i])-hash;
        int qr=std::lower_bound(hash+1,hash+cnt+1,ar[i])-hash;
        modify(1,1,cnt,ql,qr,i);
    }
    int Ans=0;
    vis[0]=1;
    cover(1,1,cnt);
    for(int i=1;i<=cnt;i++) if(!vis[ans[i]]) Ans++,vis[ans[i]]=1;
    printf("%d
",Ans);
    return 0;
}