题目回顾

我们需要计算平面上若干互不相交的垂直线段中，能够构成“线段三角形”的数量。构成“线段三角形”的条件是：三个不同的垂直线段两两之间都是水平可见的。

解题思路

1. 水平可见性判断：

   • 两条线段 $i$ 和 $j$ 是水平可见的，当且仅当：
     • 它们的 Y 区间有重叠（即 $[y_i', y_i'']$ 和 $[y_j', y_j'']$ 有交集）。
     • 在它们的 X 坐标之间没有其他线段阻挡（即没有其他线段的 X 坐标位于 $x_i$ 和 $x_j$ 之间，并且其 Y 区间与 $i$ 和 $j$ 的 Y 区间重叠）。

2. 扫描线算法：

   • 按 X 坐标从小到大排序所有线段。
   • 使用线段树维护当前活跃的线段（即已经处理过但可能阻挡后续线段的线段）。
   • 对于每条新线段，查询其 Y 区间内是否有其他线段阻挡，并更新线段树。

3. 三元环计数：

   • 将水平可见关系建模为无向图的邻接矩阵 vis，其中 vis[i][j] = 1 表示线段 $i$ 和 $j$ 水平可见。
   • 统计图中所有三元环的数量，即满足 vis[i][j] && vis[i][k] && vis[j][k] 的三元组 $(i, j, k)$。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int maxn=8005;
struct Node{ 
    int y1,y2,x;
    bool operator<(const Node&a)const
    {
       return x<a.x; 
    }
}node[maxn];
bool vis[maxn][maxn];
int lazy[maxn<<3],t,n;
void pushDown(int p)
{
   if(lazy[p])
   {
      lazy[ls]=lazy[rs]=lazy[p];
      lazy[p]=0; 
   } 
}
void query(int p,int l,int r,int L,int R,int x)
{
   if(lazy[p])
   {
      vis[lazy[p]][x]=vis[x][lazy[p]]=1;
      return; 
   } 
   if(l==r)return;
   pushDown(p);
   int mid=l+r>>1;
   if(L<=mid)query(lson,L,R,x);
   if(R>mid)query(rson,L,R,x);
}
void update(int p,int l,int r,int L,int R,int x)
{
   if(L<=l&&r<=R){ 
       lazy[p]=x;
       return;
   }
   pushDown(p);
   int mid=l+r>>1;
   if(L<=mid)update(lson,L,R,x);
   if(R>mid)update(rson,L,R,x);
}
int main()
{
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);
      for(int i=1;i<=n;++i)
         for(int j=1;j<=n;++j)
            vis[i][j]=0;
      int mx=-1;
      for(int i=1;i<=n;++i)
         scanf("%d%d%d",&node[i].y1,&node[i].y2,&node[i].x),mx=max(mx,node[i].y2);
      mx<<=1;
      for(int i=0;i<=4*mx;++i)
          lazy[i]=0;
      sort(node+1,node+1+n);
      for(int i=1;i<=n;++i)
      {
         query(1,0,mx,2*node[i].y1,2*node[i].y2,i);
         update(1,0,mx,2*node[i].y1,2*node[i].y2,i);
      } 
      ll ans=0;
      for(int i=1;i<=n;++i)
          for(int j=i+1;j<=n;++j)
          {
             if(!vis[i][j])continue;
             for(int k=i+1;k<j;++k)
                 if(vis[i][k]&&vis[j][k])
                     ans++;
          }
      printf("%lld\n",ans);
   } 
   return 0; 
}