POJ1436

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

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

解题思路：基于y轴建立线段树。

如图是根据样例画出的图。下面都以题目样例为例。

但是，如果仅仅以给出的y1, y2为边界的话会出现线段的最右点被当成一小段线段的问题，样例中的x=4的线段和x=1的线段会被判定“不可见”。为了方便处理边界情况，我们把y1和y2都乘2再存入线段树中，这也是用线段树解决问题的时候常用的处理边界争议的方法。

在每次存入线段的时候，先检查一下已有的线段树，看看以我们要存入的线段的端点[y1,y2]为边界的线段上是否已有线段，如果有，以一个二维数组记录起来。最后以几个for循环来得出ans。

注意： 用bool型代替int型可节省很多空间 。一开始那个link[ ][ ]数组我是用int型的，然后提交的时候一直MLE，后来看了网上的题解，知道了这个点，把int改成bool就AC了。

AC代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int y=8000*2;

const int maxn=8000+5;

int tree[y<<2];

bool link[maxn][maxn];

struct side{

    int y1,y2,x;

    bool operator <(const side &a)const{

        return x<a.x;

    }

}tmp[maxn];

void pushdown(int rt){

    tree[rt<<1]=tree[rt<<1|1]=tree[rt];

    tree[rt]=-1;

}

void build(int L,int R,int x,int l,int r,int rt){

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

        tree[rt]=x;

        return;

    }

    if(l==r)    return;

    if(tree[rt]!=-1)

        pushdown(rt);

    if(L<=(l+r)/2)    build(L,R,x,l,(l+r)/2,rt<<1);

    if((l+r)/2<R) build(L,R,x,(l+r)/2+1,r,rt<<1|1);

}

void query(int L,int R,int index,int l,int r,int rt){

    if(tree[rt]!=-1){

        link[tree[rt]][index]=true;

        return;

    }

    if(l==r)

        return;

    if(L<=(l+r)/2)    query(L,R,index,l,(l+r)/2,rt<<1);

    if((l+r)/2<R) query(L,R,index,(l+r)/2+1,r,rt<<1|1);

}

int main(){

    int n,ans;

    int d,i,j;

    scanf("%d",&d);

    while(d--){

        memset(tree,-1,sizeof(tree));

        memset(link,false,sizeof(link));

        scanf("%d",&n);

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

            scanf("%d%d%d",&tmp[i].y1,&tmp[i].y2,&tmp[i].x);

        sort(tmp,tmp+n);

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

            query(tmp[i].y1*2,tmp[i].y2*2,i,0,y,1);

            build(tmp[i].y1*2,tmp[i].y2*2,i,0,y,1);

        }

        ans=0;

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

            for(j=i+1;j<n;j++){

                if(link[i][j]){

                    for(int k=i+1;k<j;k++){

                        if(link[i][k]&&link[k][j])

                            ans++;

                    }

                }

            }

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

    }

    return 0;

}