Mayor's posters POJ - 2528 线段树（离散化处理大数？）

题意：输入t组数据，输入n代表有n块广告牌，按照顺序贴上去，输入左边和右边到达的地方，问贴完以后还有多少块广告牌可以看到（因为有的被完全覆盖了）。

思路：很明显就是线段树更改区间，不过这个区间的跨度有点大（看数据），不过n<10000，所以就可以把这些广告牌的边界重新定义编号，比如：

n输入 2

1 6

2 13

排序以后，1还是1，2还是2，6就可以看成3，13就可以看成4

变成：

1 3

2 4

其实性质还是没有变，两个广告牌都可以看到，不过线段树开的数组就不用很大了。

#include<algorithm>

#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

int ans,book[20010],index[10000005],sum[400010],lazy[400010],a[10010],b[10010],c[20010];

void pushdown(int l,int r,int o)

{

    if(lazy[o])

    {

        lazy[o<<1]=lazy[o<<1|1]=lazy[o];

        sum[o<<1|1]=sum[o<<1]=lazy[o];

        lazy[o]=0;

    }

}

void update(int l,int r,int o,int x,int y,int c)

{

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

    {

        sum[o]=c;

        lazy[o]=c;

        return;

    }

    pushdown(l,r,o);

    int mid=(l+r)/2;

    if(x<=mid) update(l,mid,o<<1,x,y,c);

    if(y>mid) update(mid+1,r,o<<1|1,x,y,c);

}

void query(int l,int r,int o)

{

    if(l==r)

    {

        if(!book[sum[o]])

        {

            ans++;

            book[sum[o]]=1;

        }

        return;

    }

    pushdown(l,r,o);

    int mid=(l+r)/2;

    query(l,mid,o<<1);

    query(mid+1,r,o<<1|1);

}

int main()

{

    int t,n,x,y;

    scanf("%d",&t);

    while(t--)

    {

        memset(book,0,sizeof(book));

        memset(sum,0,sizeof(sum));

        memset(lazy,0,sizeof(lazy));

        scanf("%d",&n);

        int w=0;

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

        {

            scanf("%d%d",&a[i],&b[i]);

            c[w++]=a[i];

            c[w++]=b[i];//重新编号

        }

        sort(c,c+w);

        int cnt=0;

        for(int i=0;i<w;i++)

            if(c[i]!=c[i+1])

                index[c[i]]=++cnt;

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

        {

            x=index[a[i]];

            y=index[b[i]];

            update(1,cnt,1,x,y,i);

        }

        ans=0;

        query(1,cnt,1);

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

    }

    return 0;

}

巴特西

Mayor's posters POJ - 2528 线段树（离散化处理大数？）

最新文章

热门文章