Mayor's posters-POJ2528 区间染色+离散化

题意：

在一面长度为10000000 的墙上贴广告，告诉你每张海报的l,r（1 <= l_i <= ri <= 10000000.），让你求最后有几张海报露出来

链接：http://poj.org/problem?id=2528

思路：

由于数据较大，直接开数组不现实，所以我们考虑将每个点离散化，由于这里可能存在原本不相邻的点在离散化后变成相邻

例如三张海报分别为1-5,1-2,4-5，将数据离散化后1,2,4,5分别对应1,2,3,4，此时我们发现用离散化之后的数据得出来的结果

是2，但是实际上可以看到的海报为3，所以当a[i]-a[i-1]>1时，我们要再加入a[i-1]+1,这样就能避免上述情况。

所以，这道题就变成了离散化+线段树区间染色

代码：

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <vector>

#include <math.h>

#include <string.h>

#include <map>

using namespace std;

const int MAXN=5e4+;

typedef long long ll;

int l_[MAXN],r_[MAXN],lsh[MAXN<<],visit[MAXN],lazy[MAXN<<];

void push_down(int node)

{

    lazy[node<<]=lazy[node];

    lazy[node<<|]=lazy[node];

    lazy[node]=;

}

void update(int node,int l,int r,int x,int y,int k)

{

    if(x<=l&&y>=r)

    {

        lazy[node]=k;

        return;

    }

    if(lazy[node])

        push_down(node);

    int mid=(l+r)>>;

    if(x<=mid)

        update(node<<,l,mid,x,y,k);

    if(y>mid)

        update(node<<|,mid+,r,x,y,k);

}

int ans=;

void query(int node,int l,int r,int x,int y)

{

    if(lazy[node])

    {

        if(!visit[lazy[node]])

            ans++,visit[lazy[node]]=;

        return;

    }

    if(l==r)

        return;

    int mid=(l+r)>>;

    if(x<=mid)

        query(node<<,l,mid,x,y);

    if(y>mid)

        query(node<<|,mid+,r,x,y);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(lazy,,sizeof(lazy));

        memset(visit,,sizeof(visit));

        ans=;

        int n;

        scanf("%d",&n);

        int index=;

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

        {

            scanf("%d%d",&l_[i],&r_[i]);

            lsh[index++]=l_[i],lsh[index++]=r_[i];

        }

        sort(lsh,lsh+index);

        int temp=index;

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

            if(lsh[i]-lsh[i-]>)

                lsh[index++]=lsh[i-]+;

        int cnt=unique(lsh,lsh+index)-lsh;

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

        {

            l_[i]=lower_bound(lsh,lsh+cnt,l_[i])-lsh+;

            r_[i]=lower_bound(lsh,lsh+cnt,r_[i])-lsh+;

            update(,,cnt,l_[i],r_[i],i);

        }

        query(,,cnt,,cnt);

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

    }

    return ;

}

巴特西

Mayor's posters-POJ2528 区间染色+离散化

最新文章

热门文章