hdu 5862 Counting Intersections多校第十场

题意：
给你 n 条平行于坐标轴的线段，判断线段之间的交点有多少。无重合线段，任意两条线段之间无相同端点。
官方题解：
由于数据限制,只有竖向与横向的线段才会产生交点,所以先对横向线段按x端点排序,每次加入一个线段,将其对应的 y 坐标位置+1,当出现一个竖向线段时,查询它的两个y端点之间的和即为交点个数.
解题思路：
树状数组
首先将这些点离散化，然后处理线段时将点分为三种类型。将横向线段的两个端点拆开。左端点记为0，右端点记为2，竖向线段的端点记为1（查询要在删点之前进行）。排序时按 x 端点排序，在遍历点时按类型进行不同的操作。
树状数组记录的是纵坐标的值。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define inf 0x3f3f3f3f
#define debug puts("-----")
#define ll long long
#define LL long long
const int maxn=300000+100;
ll c[maxn*4];
int val[maxn*4];
struct node
{
int x1,y1,x2,y2;
int type;
}p[maxn];
struct point        ///记录处理之后的点的信息
{
int x,l,r,type; /// x：x坐标的值，l，r：记录y坐标值，type：类型
    point(){}
    point(int a,int b,int c,int d):x(a),l(b),r(c),type(d){}
}g[maxn*4];
bool cmp(point a,point b)
{
if(a.x==b.x)
return a.type<b.type;
else return a.x<b.x;
}
int lowbit(int x)
{
return x&(-x);
}
void updata(int i,int x)
{
while(i<=maxn*4)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}
ll sum(int i)
{
    ll res=0;
while(i>0)
    {
        res+=c[i];
        i-=lowbit(i);
    }
return res;
}
int main()
{

int T;
scanf("%d",&T);
int n;
while(T--)
    {
scanf("%d",&n);
int cnt=0;
int tmp;
for(int i=0;i<n;i++)
       {
scanf("%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
if(p[i].x1==p[i].x2)
           {
               val[cnt++]=p[i].y1;
               val[cnt++]=p[i].y2;
               val[cnt++]=p[i].x1;
if(p[i].y1>p[i].y2)
               {
                   tmp=p[i].y1;
                   p[i].y1=p[i].y2;
                   p[i].y2=tmp;
               }
               p[i].type=1;
           }
else
           {
               val[cnt++]=p[i].x1;
               val[cnt++]=p[i].x2;
               val[cnt++]=p[i].y1;
if(p[i].x1>p[i].x2)
               {
                   tmp=p[i].x1;
                   p[i].x1=p[i].x2;
                   p[i].x2=tmp;
               }
               p[i].type=0;
           }
       }
       sort(val,val+cnt);
       cnt=unique(val,val+cnt)-val;///去重
int pcnt=0;
for(int i=0;i<n;i++)
       {
if(p[i].type==0)
           {
               p[i].x1=lower_bound(val,val+cnt,p[i].x1)-val+2;///在查询的时候要减一，所以这里加二避免树状数组中传入0
               p[i].x2=lower_bound(val,val+cnt,p[i].x2)-val+2;
               p[i].y1=p[i].y2=lower_bound(val,val+cnt,p[i].y1)-val+2;
               g[pcnt++]= point(p[i].x1,p[i].y1,p[i].y1,0);///左端点标记为0
               g[pcnt++]= point(p[i].x2,p[i].y1,p[i].y1,2);///右端点标记为2
           }
else
           {
               p[i].y1=lower_bound(val,val+cnt,p[i].y1)-val+2;
               p[i].y2=lower_bound(val,val+cnt,p[i].y2)-val+2;
               p[i].x2=p[i].x1=lower_bound(val,val+cnt,p[i].x1)-val+2;
               g[pcnt++]= point(p[i].x1,p[i].y1,p[i].y2,1);
           }
       }
       sort(g,g+pcnt,cmp);
        ll ans=0;
memset(c,0,sizeof(c));
for(int i=0;i<pcnt;i++)
        {
if(g[i].type==0)
            {
                updata(g[i].l,1);
            }
else if(g[i].type==1)
            {
                ans+=sum(g[i].r)-sum(g[i].l-1);
            }
else updata(g[i].l,-1);
        }
printf("%I64d\n",ans);
    }
return 0;
}