首页 > 代码库 > POJ 2528 Mayor's posters --线段树+离散化

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

2024-07-18 20:20:03   217人阅读

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

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飘过~）

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <map>#include <set>using namespace std;#define N 10007int 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

 


联系
我们