每三条在水平上可以互相望见的竖线段可以组成一个三角形,求三角形总数.

开始看完题目后觉得不难写,扫描线,更改前查询.写完对照例子发现无论是把节点作为点还是线段,总是会有疏忽的情况,样例果然强大阿.才终于领悟大牛博客上说的纵坐标*2会简单,看来是奇数点可以保存线段的颜色信息,这样节点作为点就没问题了.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 8000
#define lcd root<<1
#define rcd root<<1|1
vector<int> con[maxn];
int last[maxn];
struct seg 
{
    int x,y1,y2;
    bool operator < (const seg &s) const
    {return x<s.x;}
} s[maxn];
struct node
{
    int l,r,id;
    int mid(){return (l+r)>>1;}
}tree[16000*3];
void build(int l,int r,int root)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].id=-1;//-1:none -2:mix
    if(l==r) return;
    int m=(l+r)>>1;
    build(l,m,lcd);
    build(m+1,r,rcd);
}
void down(int root)
{
    if(tree[root].id!=-2)
    {
        tree[lcd].id=tree[rcd].id=tree[root].id;
        tree[root].id=-2;
    }
}
void update(int l,int r,int id,int root)
{
    if(tree[root].l==l && tree[root].r==r)
    {
        tree[root].id=id;
        return;
    }
    if(tree[root].l==tree[root].r) return;
    down(root);
    int m=tree[root].mid();
    if(r<=m) update(l,r,id,lcd);
    else if(l>m) update(l,r,id,rcd);
    else
        update(l,m,id,lcd),update(m+1,r,id,rcd);
}
void query(int l,int r,int id,int root)
{
    if(tree[root].id!=-2)
    {
        int id2=tree[root].id;
        if(id2!=-1) if(last[id2]!=id)
        {
            con[id].push_back(id2);
            last[id2]=id;
        }
        return;
    }
    if(tree[root].l==tree[root].r) return;
    down(root);
    int m=tree[root].mid();
    if(r<=m) query(l,r,id,lcd);
    else if(l>m) query(l,r,id,rcd);
    else
        query(l,m,id,lcd),query(m+1,r,id,rcd);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&s[i].y1,&s[i].y2,&s[i].x);
            s[i].y1<<=1; s[i].y2<<=1;
        }
        sort(s,s+n);
        build(0,16000,1);
        for(int i=0;i<n;i++) con[i].clear();
        memset(last,-1,sizeof(last));
        for(int i=0;i<n;i++)
        {
            if(i) query(s[i].y1,s[i].y2,i,1);
            update(s[i].y1,s[i].y2,i,1);
        }
        int ans=0;
        for(int i=0;i<n;i++)
            for(int l=0;l<con[i].size();l++)
            {
                int j=con[i][l];
                for(int l2=0;l2<con[i].size();l2++)
                {
                    int k=con[i][l2];
                    if(k>j) for(int l3=0;l3<con[k].size();l3++)
                        if(con[k][l3]==j) 
                            ++ans;
                }
            }
        printf("%d\n",ans);
    }
}