poj 1436 Horizontally Visible Segments[線段樹]

/*
poj 1436 題意:
給出N(N <= 8000)條垂直線段，如果兩條線段在水準方向上連一條線之後不和其他任
何垂直線段相交，那麼我們稱這兩條線段水準可見，如果三條垂直線段兩兩水準可見
，則稱其為一個三角，問着N條線段能組成多少三角。
解法:
線段樹記錄線段的id号。先将每一條線段按照x坐标排序，然後對于每一條線段，
先查詢之前在它覆寫的區域内能看見哪些線段沒有被完全覆寫，然後再用這條線段去更新。
最後暴力統計,*/
           

//ps:太弱。。。且一直糾結于為什麼要将y坐标*2.。。終于發現了，,0,2,2,3,4,2這兩組資料中間是可以通過的，但是中間确實可以通過...是以*2就能解決這個問題..^_^
           

//這題其實也不難...線段樹+枚舉...額,,偶太弱>_<
           

#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>

using namespace std;
typedef struct even{int y1,y2,x;}even;

#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 16666
even edge[maxn];
int col[maxn<<2];
int seg[maxn<<2];
int hash[maxn+1];
vector<int>V[maxn];
int cmp( const void *a , const void *b ) {
    struct even *c = (even *)a;
    struct even *d = (even *)b;
    return c->x - d->x;
}
void pushdown(int rt){
    if(col[rt]!=-1){
        col[rt<<1|1]=col[rt<<1]=col[rt];
        col[rt]=-1;
    }
}
void update(int c,int L,int R,int l,int r,int rt){
    if(l>=L&&r<=R){
        col[rt]=c;
        return ;
    }
    pushdown(rt);
    if(l==r) return ;
    int m=(l+r)>>1;
    if(L<=m) update(c,L,R,lson);
    if(R>m) update(c,L,R,rson);
}
void query(int c,int L,int R,int l,int r,int rt){
    if(col[rt]!=-1){
        if(hash[col[rt]]!=c){
            V[col[rt]].push_back(c);
            hash[col[rt]]=c;
        }
        return ;
    }
    pushdown(rt);
    if(l==r) return ;
    int m=(l+r)>>1;
    if(L<=m){
        query(c,L,R,lson);
    }
    if(R>m){
        query(c,L,R,rson);
    }
}
int main(){
    int d,n;
    scanf("%d",&d);
    while(d--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&edge[i].y1,&edge[i].y2,&edge[i].x);
            edge[i].y1<<=1;
            edge[i].y2<<=1;
            V[i].clear();
        }
        qsort(edge,n,sizeof(edge[0]),cmp);
        memset(col,-1,sizeof(col));
        memset(hash,-1,sizeof(hash));
        for(int i=0;i<n;i++){
            query(i,edge[i].y1,edge[i].y2,0,maxn,1);
            update(i,edge[i].y1,edge[i].y2,0,maxn,1);
        }
        int sum=0;
/*      FOR(ii,0,n) {
            FOR(jj,0,V[ii].size()){
                printf("%d ",V[ii][jj]);
                }
                puts("");
            }
*/
        for(int i=0;i<n;i++){
            for(int j=0;j<V[i].size();j++){
                int k=V[i][j];
                for(int t=0;t<V[i].size();t++){
                    for(int w=0;w<V[k].size();w++)
                    if(V[i][t]==V[k][w]) sum++;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}