Description

　　There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments? 

 

　　题意大致就是说给你一些线段，问相邻两个线段有没有公共的部分，且没有其他线段阻挡。

　　

　　首先对x排序，然后枚举，对于每个线段，先询问这个区间上的所有其他线段，然后再覆盖更新。

　　对于COL数组，如果为-1表示这个区间上有多个线段，否则的话表示的是线段的编号（这里假设先放了一个编号为0的线段。）

　　（PS：我能说这个题我调试了一下午吗，刚开始把COL设置为了bool的变量，结果。。。T T ， 一直没找出错误来。。。痛苦。。。）

 

代码如下：

#include
       
        #include
        
         #include
         
          #include
          
           #define lson L,M,po*2#define rson M+1,R,po*2+1using namespace std;const int N=8000*2;int COL[8008*2*4];bool map1[8008][8008];void pushDown(int po){    if(COL[po]>=0)    {        COL[po*2]=COL[po*2+1]=COL[po];        COL[po]=-1;    }}void update(int ul,int ur,int ut,int L,int R,int po){    if(ul<=L&&ur>=R)    {        COL[po]=ut;        return;    }    pushDown(po);    int M=(L+R)/2;    if(ul<=M)        update(ul,ur,ut,lson);    if(ur>M)        update(ul,ur,ut,rson);    if(COL[po*2]==COL[po*2+1])          //这里算是一个剪枝操作，可以减少递归次数。        COL[po]=COL[po*2];    else        COL[po]=-1;}void query(int ql,int qr,int qt,int L,int R,int po){    if(COL[po]!=-1)    {        map1[qt][COL[po]]=map1[COL[po]][qt]=1;        return;    }    if(L==R)        return;    int M=(L+R)/2;    if(ql<=M)        query(ql,qr,qt,lson);    if(qr>M)        query(ql,qr,qt,rson);}struct state{    int y1,y2,x1;};state sta[8008];int cmp(const void*a,const void*b){    return (*(state*)a).x1-(*(state*)b).x1;}int main(){    int d;    cin>>d;    int n;    while(d--)    {        memset(map1,0,sizeof(map1));        memset(COL,0,sizeof(COL));        cin>>n;        for(int i=0;i