首页 > 其他 > 详细

POJ 2528 Mayor's posters --线段树+离散化

时间:2014-08-21 22:28:04      阅读:453      评论:0      收藏:0      [点我收藏+]

题意:不讲了,线段树离散化的入门题。之所以贴出来只为吐槽几个地方:

1.最后统计颜色的时候,试了好几种方法都TLE,反正用vis就TLE,不知道别人的怎么行,最后没办法,学了网上一个机智的做法:用set记录ans个数,最后过了。

2.数据不对,离散化的时候如果排完序后相邻的元素值不相邻的话,是不能离散为相邻的两个元素的,比如数据:

3

1 10 

1 3

6 10

答案应该为3,而普通离散化后的线段变为了 [1,4], [1,2], [3,4],就是说[1,4]被其他两个线段给覆盖了,输出为2,这是不对的,但是POJ竟然可以过。一个字,水!

代码: (922ms飘过~)

bubuko.com,布布扣
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define N 10007
int L[N],R[N],line[2*N];
int tree[16*N],vis[N];
map<int,int> mp;
set<int> ans;

void build(int l,int r,int rt)
{
    tree[rt] = 0;
    if(l == r) return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}

void pushdown(int rt,int col)
{
    if(tree[rt] != col && tree[rt] > 0)
    {
        tree[2*rt] = tree[2*rt+1] = tree[rt];
        tree[rt] = 0;
    }
}

void update(int l,int r,int aa,int bb,int col,int rt)
{
    if(aa <= l && bb >= r)
    {
        tree[rt] = col;
        return;
    }
    pushdown(rt,col);
    int mid = (l+r)/2;
    if(aa <= mid)
        update(l,mid,aa,bb,col,2*rt);
    if(bb > mid)
        update(mid+1,r,aa,bb,col,2*rt+1);
}

int query(int l,int r,int rt)    //Time Limit Exceeded
{
    if(tree[rt])
    {
        if(!vis[tree[rt]])
        {
            vis[tree[rt]] = 1;
            return 1;
        }
        return 0;
    }
    if(l == r)
        return 0;
    int mid = (l+r)/2;
    return query(l,mid,2*rt) + query(mid+1,r,2*rt+1);
}

int res;
void Q(int l,int r,int rt)     //Time Limit Exceeded
{
    if(tree[rt])
    {
        if(!vis[tree[rt]])
        {
            vis[tree[rt]] = 1;
            res++;
        }
        return;
    }
    if(l == r)
        return;
    int mid = (l+r)/2;
    Q(l,mid,2*rt);
    Q(mid+1,r,2*rt+1);
}

void SUM(int l,int r,int rt)     //Accepted
{
    if(tree[rt])
    {
        ans.insert(tree[rt]);
        return;
    }
    if(l == r)
        return;
    int mid = (l+r)/2;
    SUM(l,mid,2*rt);
    SUM(mid+1,r,2*rt+1);
}

int main()
{
    int t,n,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        mp.clear();
        ans.clear();
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&L[i],&R[i]);
            line[2*i-1] = L[i];
            line[2*i] = R[i];
        }
        sort(line+1,line+2*n+1);
        int ind = unique(line+1,line+2*n+1)-line-1;
        int now = 0;
        mp[line[1]] = ++now;
        for(i=2;i<=ind;i++)
        {
            if(line[i] > line[i-1]+1)
                mp[line[i]] = now+2,now+=2;
            else if(line[i] == line[i-1] + 1)
                mp[line[i]] = ++now;
        }
        build(1,now,1);
        for(i=1;i<=n;i++)
            update(1,now,mp[L[i]],mp[R[i]],i,1);
        SUM(1,now,1);
        printf("%d\n",ans.size());
    }
    return 0;
}
View Code

 

POJ 2528 Mayor's posters --线段树+离散化,布布扣,bubuko.com

POJ 2528 Mayor's posters --线段树+离散化

原文:http://www.cnblogs.com/whatbeg/p/3928078.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!