poj 2528 Mayor's posters【离散化+线段树】

比眉伴天荒 2022-08-10 17:54 178阅读 0赞

题目：[poj 2528 Mayor's posters][poj 2528 Mayor_s posters]

题意：给一个长度非常长的墙上贴长度为ai的海报，由于有的会覆盖掉，求最后能看见的海报个数。

分析：题目和POJ2777 一模一样，方法也一样，只不过这个要离散化，其次要数组开大一点。至少2倍。

离散化的时候用了C++的 pair 类，还是比较好用的。

代码：

#include <iostream>
    #include <algorithm>
    #include <utility>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    const int N = 25000;
    pair<int,int> p[2*N];
    pair<int,int> v[N];
    int n;
    int comp(pair<int,int> a,pair<int,int> b)
    {
        if(a.first!=b.first)
            return a.first<b.first;
    }
    int cmp(pair<int,int> a,pair<int,int> b)
    {
        if(a.second!=b.second)
            return a.second<b.second;
        if(a.first!=b.first)
            return a.first<b.first;
    }
    int Discrete()  //离散化
    {
        for(int i=0; i<n; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            p[i*2]=make_pair(x,i);
            p[i*2+1]=make_pair(y,i);
        }
        sort(p,p+2*n,comp);
        int cnt=2,tmp=p[0].first;
        p[0].first=1;
        for(int i=1; i<n*2; i++)
        {
            if(p[i].first==tmp)
            {
                tmp=p[i].first;
                p[i].first=(cnt-1);
            }
            else
            {
                tmp=p[i].first;
                p[i].first=cnt++;
            }
        }
        sort(p,p+2*n,cmp);
        for(int i=0; i<2*n; i+=2)
            v[i/2]=make_pair(p[i].first,p[i+1].first);
        cnt--;
        return cnt;
    }
    struct Node
    {
        int l,r;
        long long num;
    };
    Node tree[4*N];
    int vis[N*2];
    void build(int l,int r,int o)
    {
        tree[o].l=l;
        tree[o].r=r;
        tree[o].num=1;
        if(l==r)
            return ;
        int mid=(l+r)/2;
        build(l,mid,o*2);
        build(mid+1,r,o*2+1);
    }
    void update(int l,int r,int t,int o)
    {
        if(tree[o].l==l && tree[o].r==r)
        {
            tree[o].num=t;
            return;
        }
        if(tree[o].num==t) return;
        if(tree[o].num!=-1)
        {
            tree[2*o].num=tree[o].num;
            tree[2*o+1].num=tree[o].num;
            tree[o].num=-1;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(r<=mid)
            update(l,r,t,o+o);
        else if(l>mid)
            update(l,r,t,o+o+1);
        else
        {
            update(l,mid,t,o*2);
            update(mid+1,r,t,o*2+1);
        }
    }
    void query(int l,int r,int o)
    {
        if(tree[o].num!=-1)
        {
            vis[tree[o].num]=1;
            return ;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(r<=mid)
            query(l,r,o+o);
        else if(l>mid)
            query(l,r,o+o+1);
        else
        {
            query(l,mid,o*2);
            query(mid+1,r,o*2+1);
        }
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            int cnt=Discrete();
            build(1,cnt,1);
            for(int i=0;i<n;i++)
            {
                update(v[i].first,v[i].second,i,1);
            }
            memset(vis,0,sizeof(vis));
            query(1,cnt,1);
            int ans=0;
            for(int i=0;i<=cnt;i++)
                if(vis[i]){
                    //printf("--%d ",i);
                    ans++;
                }
            printf("%d\n",ans);
            memset(p,0,sizeof(p));
            memset(v,0,sizeof(v));
        }
        return 0;
    }

[poj 2528 Mayor_s posters]: http://poj.org/problem?id=2528