1682. [HAOI2014]贴海报

★★☆ 输入文件：ha14d.in 输出文件：ha14d.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

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

张贴规则如下：

1．electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；

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

3．每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；

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

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

【输入格式】

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

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

【输出格式】

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

【样例输入】

100 5

1 4

2 6

8 10

3 4

7 10

【样例输出】

【提示】

【约束条件】

1 0<= N <= 10000000 1<=M<=1000 1<= Ai <= Bi <=10000000

所有的数据都是整数。数据之间有一个空格

思路:

　　1）首先这道题暴力可以拿80分！（在luogu上可以AC！！！！）

　　2）然后考场上作死写了个并查集。。。61分

　　3）正解:

　　　　　　①线段树（然而我没写~）

　　　　　　②浮水法

坑点:

　　因为给出的是所位于的块，不是左右端点，所以在处理浮水法的时候记得要右端点+1，或者左端点-1

上代码:

1）暴力

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

using namespace std;

const int M = 1e7 + ;

int n,m,l,r,ans;

int a[M],v[M];

inline int reads()

{

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'')

    {if(ch=='-') f=-;ch=getchar();}

    while(ch>='' && ch<='')

    {x=*x+ch-'';ch=getchar();}

    return x*f;

}

int main()

{

    freopen("ha14d.in","r",stdin);

    freopen("ha14d.out","w",stdout);

    n=reads(),m=reads();

    for(int i=;i<=m;i++)

    {

        l=reads(),r=reads();

        if(r<l) swap(l,r);

        for(int j=l;j<=r;j++)

            a[j]=i;

    }

    for(int i=;i<=n;i++)

    {

        if(!v[a[i]] && a[i])

        {

            ans++;

            v[a[i]]=;

        }

    }

    printf("%d",ans);

    return ;

}

2）作死并查集

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

using namespace std;

inline int reads()

{

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'')

    {if(ch=='-') f=-;ch=getchar();}

    while(ch>='' && ch<='')

    {x=*x+ch-'';ch=getchar();}

    return x*f;

}

const int M = 1e7 + ;                ///多开几个

const int N = ;

int n,m;

int f[M];

int ans[M],anse;

int Ls[N],Rs[N];

int getf(int x)

{return f[x] == x ? x : f[x] = getf(f[x]);}

int main()

{

    freopen("ha14d.in","r",stdin);

    freopen("ha14d.out","w",stdout);

    n=reads();m=reads();                    ///n是n块,不是左右端点!!!

    for(int i=;i<=n+;i++)

        f[i]=i;

    for(int i=;i<=m;i++)                   ///m组数据

    {                                       ///手动从1开始,从0不会...

        Ls[i]=reads();

        Rs[i]=reads()+;                    ///因为给出不是点的坐标,是块的坐标

    }

    int l,r;

    for(int i=m;i>=;i--)                   ///逆序张贴,因为只需要的是最后的能看到的海报

    {

        l=Ls[i],r=Rs[i];                    ///左右端点

        if(l>r) swap(l,r);                  ///maybe?会出现"left">"right"的情况(考虑最坏情况,以防万一,以前做过一个题就是恶心的数据!)

        for(int j=getf(l);j<=r;j=getf(j+))

        {

            f[getf(j)]=getf(j+);           ///将当前被张贴报纸的父结点手动设置到最后一个的父结点

///            ans[j]=i;

            ans[i]++;

            if(getf()==n+) break;         ///表示已经贴完

        }

    }

    for(int i=;i<=n+;i++)

    {

///        printf("%d=%d\n",i,ans[i]);      ///输出调试???

        if(ans[i]) anse++;

    }

    printf("%d\n",anse);

    return ;

}

3）正解（浮水法）

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

const int M = ;

int n,m,ans=;

bool v[M];

struct U {

    int l,r,id;

    //id 为第几张海报

}t[M];

inline int reads()

{

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'')

    {if(ch=='-') f=-;ch=getchar();}

    while(ch>='' && ch<='')

    {x=*x+ch-'';ch=getchar();}

    return x*f;

}

void swim(int ql,int qr,int nowid,int preid)

{

    if(v[preid])

        return;

    while(nowid<=m && (qr<=t[nowid].l || ql>=t[nowid].r))

        nowid++;

    if(nowid>m)

    {

        v[preid]=true;

        ans++;

        return;

    }

    if(ql<t[nowid].l && qr>t[nowid].l)

        swim(ql,t[nowid].l,nowid+,preid);

    if(ql<t[nowid].r && qr>t[nowid].r)

        swim(t[nowid].r,qr,nowid+,preid);

}

int main()

{

    freopen("ha14d.in","r",stdin);

    freopen("ha14d.out","w",stdout);

    n=reads();m=reads();

    for(int i=;i<=m;i++)

    {

        t[i].l=reads(),t[i].r=reads()+;

        t[i].id=i;

    }

    for(int i=m-;i>=;i--)

        swim(t[i].l,t[i].r,i+,i);

    printf("%d",ans);

    return ;

}

巴特西

cogs1682. [HAOI2014]贴海报 x