ZOJ 2301/HDU 1199 线段树+离散化

给这个题目跪了两天了，想吐简直

发现自己离散化没学好

包括前一个离散化的题目，实际上是错了，我看了sha崽的博客后才知道，POJ那题简直数据弱爆了，本来随便一组就能让我WA掉的，原因在于离散化的时候，缩小数据规模的同时，没有考虑到误差，比如 1 4 6 8，离散化之后是1 2 3 4，我如果覆盖了1 2和3 4，表面上好像全部覆盖了，实际数据并没有覆盖。。所以我只能说那道题目我其实错了，并没有真正做出离散化出来。。。现在用这道题来弥补。

color the ball，ball的编号可以从1 到2^31，不可能开这么大线段树，但是其实测试数据只有N=2000*2组，所以必然是离散化，初始的时候，所有球都是黑色的，然后N组数组，a b w(b)，说明把区间 a到b染成（white or black）,最后求最长的连续白色的区间的左右边界

瞬间想到上次求最大连续子串，线段树节点里用一个除了记录最大值，前驱最大值，后驱最大值以外，专门用个lm ,rm记录题目需要的坐标。这些都好处理，基本的线段树区间合并。要注意的是落实的叶子节点的时候，不能单纯以离散化之后的区间长度为衡量标准，要回到原区间去，原区间最长才是真正的最长。这个也好操作，读入数据的时候已经把原始区间保存下来了。

然后就是坑爹的离散化了，还是sha崽说得对，如果离散的两点距离大一1的话，必须要中间手动插点，以确保覆盖过程不会出现问题

而这道题目应该这样离散，如果原始的两点相差为2的话，中间插入一点就行，如果大于2的话，就要插入两点，一点为a+1，一点为b-1（假设a，b就为原始的两个点），这样求得的区间就不会出错，很简单一个事例，1 4 7 8，离散之后是1 2 3 4，先染1 4为白，再染4 8为黑，这样的话，会输出1 1为最长白色，但是明显的最大白色是1到3，所以这就是离散没有插中间点的弊端。

恩，讲完了，不得不吐槽一下，ZOJ上的这道题目数据奇坑，我说我为什么老是访问了非法内存。TMD，它输入的a b有可能a比b大。。。尼玛我加了判断之后才过得。。。。。。。。之前一直SF段错误，弄得我不明不白、

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 24010

#define Lson l,mid,rt<<1

#define Rson mid+1,r,rt<<1|1

using namespace std;

struct node

{

    int pl,pr;

    int color;

} pos[N<<];

int xl[N<<];

int mc[N<<],lc[N<<],rc[N<<];

int lm[N<<],rm[N<<];

int pd[N<<];

int ldd[N<<];

int rdd[N<<];

void getup(int rt,int l,int r)

{

    if (mc[rt<<]>=mc[rt<<|])

    {

        mc[rt]=mc[rt<<];

        lm[rt]=lm[rt<<];

        rm[rt]=rm[rt<<];

    }

    else

    {

        mc[rt]=mc[rt<<|];

        lm[rt]=lm[rt<<|];

        rm[rt]=rm[rt<<|];

    }

    lc[rt]=lc[rt<<];

    rc[rt]=rc[rt<<|];

    ldd[rt]=ldd[rt<<];

    rdd[rt]=rdd[rt<<|];

    int mid=(l+r)>>;

    if (ldd[rt<<]==mid  &&lc[rt<<|]> &&lc[rt<<]>)

    {

        lc[rt]+=lc[rt<<|];

        ldd[rt]=ldd[rt<<|];

    }

    if (rdd[rt<<|]==mid+  && rc[rt<<]>&&rc[rt<<|]>)

    {

        rc[rt]+=rc[rt<<];

        rdd[rt]=rdd[rt<<];

    }

    if (mc[rt]<rc[rt<<]+lc[rt<<|] )

    {

        mc[rt]=rc[rt<<]+lc[rt<<|];

        lm[rt]=rdd[rt<<];

        rm[rt]=ldd[rt<<|];

    }

}

void build(int l,int r,int rt)

{

    mc[rt]=lc[rt]=rc[rt]=;

    lm[rt]=rm[rt]=pd[rt]=-;

    ldd[rt]=l;

    rdd[rt]=r;

    if (l>=r)

        return;

    int mid=(l+r)>>;

    build(Lson);

    build(Rson);

    //getup(rt);

}

int bs(int data,int l,int r)

{

    int mid;

    while (l<r)

    {

        mid=(l+r)/;

        if (xl[mid]==data) return mid;

        if (xl[mid]<data) l=mid+;

        else r=mid;

    }

    return l;

}

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

{

    if (pd[rt]==- || l>=r) return;

    int mid=(l+r)>>;

    int ll=rt<<,rr=rt<<|;

    mc[ll]=lc[ll]=rc[ll]=pd[rt]*(xl[mid]-xl[l]+);

    mc[rr]=lc[rr]=rc[rr]=pd[rt]*(xl[r]-xl[mid+]+);

    if (pd[rt]==)

    {

        lm[ll]=l;

        rm[ll]=mid;

        lm[rr]=mid+;

        rm[rr]=r;

        ldd[ll]=mid;

        rdd[ll]=l;

        ldd[rr]=r;

        rdd[rr]=mid+;

    }

    else

    {

        lm[ll]=rm[ll]=lm[rr]=rm[rr]=-;

        ldd[ll]=l;

        rdd[ll]=mid;

        ldd[rr]=mid+;

        rdd[rr]=r;

    }

    pd[ll]=pd[rr]=pd[rt];

    pd[rt]=-;

}

void fix(int L,int R,int color,int l,int r,int rt)

{

    if (L<=l && r<=R)

    {

        mc[rt]=lc[rt]=rc[rt]=color*(xl[r]-xl[l]+);

        if (color==)

        {

            lm[rt]=l;

            rm[rt]=r;

            ldd[rt]=r;

            rdd[rt]=l;

        }

        else

        {

            lm[rt]=rm[rt]=-;

        }

        pd[rt]=color;

        return;

    }

    pushdown(rt,l,r);

    int mid=(l+r)>>;

    //cout<<" l is "<<l<<" r is "<<r<<" "<<endl;

    if (L>mid) fix(L,R,color,Rson);

    else

        if (R<=mid) fix(L,R,color,Lson);

    else

    if (L<=mid && R>mid)

    {

        fix(L,R,color,Lson);

        fix(L,R,color,Rson);

    }

    getup(rt,l,r);

    //cout<<mc[rt]<<" "<<" "<<lm[rt]<<" "<<rm[rt]<<" "<<lc[rt]<<" "<<rc[rt]<<endl;

}

int main()

{

    int n;

    while (scanf("%d",&n)!=EOF)

    {

        if (n==){

            puts("Oh, my god");

            continue;

        }

        int i,j;

        char ch[];

        int cur=,a,b;

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

        {

            scanf("%d%d%s",&a,&b,ch);

            pos[i].pl=a;

            pos[i].pr=b;

            xl[++cur]=a;

            xl[++cur]=b;

            if (ch[]=='w')

               pos[i].color=;

            else

               pos[i].color=;

        }

        sort(xl+,xl+cur+);

        int m=;

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

            //?printf("%d %d\n",i,xl[i]);

            if (xl[i]!=xl[i-]){

                xl[++m]=xl[i];

            }

        }

        cur=m;

        for (i=;i<=cur;i++){

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

                xl[++m]=xl[i-]+;

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

                xl[++m]=xl[i]-;

        }

        /*

        for (j=m;j>1;j--)

        {

            if (xl[j]!=xl[j-1]+1)

                xl[++m]=xl[j-1]+1;

        }

        */

        sort(xl+,xl+m+);

        //for (i=1;i<=m;i++)

            //cout<<i<<" xxx "<<xl[i]<<endl;

        build(,m,);

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

        {

             int pa=bs(pos[i].pl,,m);

             int pb=bs(pos[i].pr,,m);

             if (pa>pb){

                int temp=pa;

                pa=pb;

                pb=temp;

             }

             //if (pa<1||pa>m||pb<1||pb>m) continue;

             //cout<<pa<<" pp "<<pb<<endl;

             //

             //cout<<lm[1]<<" pass "<<rm[1]<<endl;

             fix(pa,pb,pos[i].color,,m,);

        }

        if (lm[]==-||rm[]==-)

            puts("Oh, my god");

        else

        {

            printf("%d %d\n",xl[lm[]],xl[rm[]]);

        }

    }

    return ;

}

巴特西

ZOJ 2301/HDU 1199 线段树+离散化

最新文章

热门文章