【题意】真水的题。。不知道我们队干了什么，卡在A题这个水题几个小时，太悲哀了。

【解题方法】这不好说，去偷一份我同学的解题方法吧，思路大概都是这样，扫描线的基础题了，BIT维护信息，扫描线扫过去就完了。

因为题目已经说明所有的线段都是平行于坐标轴的

那么,线段无外乎两种:①平行于x轴;②平行于y轴


那交点必定只有竖向与横向的线段才会产生

另外,此题数据规模显然是不允许我们进行O(n^2)的暴力求解

那我们可以将横向的线段与竖向线段分开处理

对于横向的线段,我们只保留端点

再按x从小到大排序,x相等的情况下,左端点优先于右端点

而竖向的线段同样按x从小到大排序,但是不拆分成两个端点,而是保留整条线段

然后枚举竖向线段,将小于该竖向线段横坐标的所有点进行处理

若点为左端点,则在其对应的值处的树状数组做+1操作,若为右端点,则做-1操作

这保证了对于第i条竖向线段,当前树状数组中记录了横坐标横跨该竖向线段的线段数量


【AC 代码】


#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
typedef long long LL;
struct bit{
    LL c[maxn];int n;
    void init(int _n){
        memset(c,0,sizeof(c));
        n=_n;
    }
    void add(int i,int v){
        while(i<=n){
            c[i]+=v;
            i+=i&-i;
        }
    }
    int getans(int i){
        int ans=0;
        while(i>0){
            ans+=c[i];
            i-=i&-i;
        }
        return ans;
    }
}BIT;
struct node1{
    int x1,y1,x2,y2;
}seg[maxn],q[maxn];
struct node2{
    int x,y,type;
}p[maxn];
bool cmp1(node2 a,node2 b){
    if(a.x!=b.x) return a.x<b.x;
    return a.type<b.type;
}
bool cmp2(node1 a,node1 b){
    return a.x1<b.x1;
}
vector<int>xs;
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        LL ans=0;
        BIT.init(maxn);
        xs.clear();
        for(int i=1; i<=n; i++){
            scanf("%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2);
            if(q[i].x1>q[i].x2||q[i].y1>q[i].y2){
                swap(q[i].x1,q[i].x2);
                swap(q[i].y1,q[i].y2);
            }
            xs.push_back(q[i].x1);
            xs.push_back(q[i].y1);
            xs.push_back(q[i].x2);
            xs.push_back(q[i].y2);
        }
        sort(xs.begin(),xs.end());
        xs.resize(unique(xs.begin(),xs.end())-xs.begin());
        int k1=0,k2=0;
        for(int i=1; i<=n; i++){
            int x1=lower_bound(xs.begin(),xs.end(),q[i].x1)-xs.begin()+1;
            int y1=lower_bound(xs.begin(),xs.end(),q[i].y1)-xs.begin()+1;
            int x2=lower_bound(xs.begin(),xs.end(),q[i].x2)-xs.begin()+1;
            int y2=lower_bound(xs.begin(),xs.end(),q[i].y2)-xs.begin()+1;
            if(y1==y2){
                p[++k1].x=x1,p[k1].y=y1,p[k1].type=0;
                p[++k1].x=x2,p[k1].y=y2,p[k1].type=1;
            }else{
                seg[++k2]=node1{x1,y1,x2,y2};
            }
        }
        sort(p+1,p+k1+1,cmp1);
        sort(seg+1,seg+k2+1,cmp2);
        //扫描线段
        for(int i=1,j=1; i<=k2; i++){
            while(j<=k1&&(p[j].x<seg[i].x1||(p[j].x==seg[i].x1&&p[j].type==0))){
                if(p[j].type==0) BIT.add(p[j].y,1);
                else BIT.add(p[j].y,-1);
                j++;
            }
            ans+=BIT.getans(seg[i].y2)-BIT.getans(seg[i].y1-1);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}