poj1436水平可见线

还是线段树区间更新，这次不需要对线段离散化，但是要把线段纵坐标*2，可以举例模拟

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 8005

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct Edge{

    int x,y1,y2,id;

    bool operator<(const Edge& a)const{

        return x<a.x;

    }

}edge[maxn];

bool mp[maxn][maxn];

int color[maxn*<<],m,ans;

inline void pushdown(int rt){

    if(color[rt]){

        color[rt<<]=color[rt<<|]=color[rt];

        color[rt]=;

    }

}

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

    if(color[rt]){

        mp[id][color[rt]]=;

        return;

    }

    if(l==r) return;

    int m=l+r>>;

    if(L<=m) query(L,R,id,lson);

    if(R>m) query(L,R,id,rson);

}

void update(int L,int R,int id,int l,int r,int rt){

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

        color[rt]=id;

        return;

    }

    pushdown(rt);

    int m=l+r>>;

    if(L<=m) update(L,R,id,lson);

    if(R>m) update(L,R,id,rson);

}

int main(){

    int T,n;

    cin >> T;

    while(T--){

        m=-;

        ans=;

        memset(color,,sizeof color);

        memset(mp,,sizeof mp);

        cin >> n;

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

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

            edge[i].y1*=;

            edge[i].y2*=;

            edge[i].id=i;

            m=max(edge[i].y1,m);

            m=max(edge[i].y2,m);

        }

        sort(edge+,edge++n);

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

            query(edge[i].y1,edge[i].y2,edge[i].id,,m,);

            update(edge[i].y1,edge[i].y2,edge[i].id,,m,);

        }

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

            for(int j=;j<=n;j++)

                if(mp[i][j])

                    for(int k=;k<=n;k++)

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

                            ans++;

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

    }

}