poj2528（线段树+离散化）

题目链接：https://vjudge.net/problem/POJ-2528

题意：在区间[1,1e7]内染色，依次染n(<=1e4)中颜色，给出每种颜色染色的范围，可重叠，求最终有多少种颜色。

思路：继续肝线段树。。被这题虐了一下午加一晚上QAQ。

　　　首先要想到离散化，因为区间为1e7，直接做的话时间空间都做不到。但因为是区间，这里不能简单的离散化，比如1、5离散化为1、2是有问题的，必须离散化为1，3，5; 还记得要先去重。

　　　其次是线段树，这道题是典型的线段树的题，直接对点操作的话复杂度很大，所以用线段树完成对区间的操作。线段树结点包括l（区间左端点）、r（区间右端点）、value（为0表示该区间没有颜色或有多种颜色，为>0表示对应的颜色编号）。

　　　最后进行一次询问即可，仅当区间的value>0时再判断颜色，并且用hash数组记录颜色i是否出现过。

AC代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

struct node{

    int l,r,value;

}tr[*maxn];

int a[maxn][],b[*maxn],T,n,hash[maxn],ans;

void build(int v,int l, int r){

    tr[v].l=l,tr[v].r=r,tr[v].value=;

    if(l==r) return;

    int mid=(l+r)>>;

    build(v<<,l,mid);

    build(v<<|,mid+,r);

}

void pushdown(int v){

    tr[v<<].value=tr[v].value;

    tr[v<<|].value=tr[v].value;

    tr[v].value=;

}

void update(int v,int l,int r,int k){

    if(l<=tr[v].l&&r>=tr[v].r){

        tr[v].value=k;

        return;

    }

    if(tr[v].value) pushdown(v);

    int mid=(tr[v].l+tr[v].r)>>;

    if(l<=mid) update(v<<,l,r,k);

    if(r>mid) update(v<<|,l,r,k);

}

void query(int v){

    if(tr[v].value){

        if(!hash[tr[v].value]){

            ++ans;

            hash[tr[v].value]=;

        }

        return;

    }

    if(tr[v].l==tr[v].r) return;

    query(v<<);

    query(v<<|);

}

int main(){

    scanf("%d",&T);

    while(T--){

        memset(hash,,sizeof(hash));

        ans=;

        scanf("%d",&n);

        int cnt1=;

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

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

            b[++cnt1]=a[i][];

            b[++cnt1]=a[i][];

        }

        sort(b+,b+cnt1+);

        int cnt2=;

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

            if(b[i]!=b[i-]) b[++cnt2]=b[i];

        int t=cnt2;

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

            if(b[i]-b[i-]>) b[++cnt2]=b[i-]+;

        sort(b+,b+cnt2+);

        build(,,cnt2);

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

            int x=lower_bound(b+,b+cnt2+,a[i][])-b;

            int y=lower_bound(b+,b+cnt2+,a[i][])-b;

            update(,x,y,i);

        }

        query();

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

    }

    return ;

}

巴特西

poj2528（线段树+离散化）

最新文章

热门文章