POJ 1436 Horizontally Visible Segments（线段树区间更新）

太过爱你忘了你带给我的痛 2022-06-10 00:09 191阅读 0赞

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?  
  
  
Task  
  
Write a program which for each data set:  
  
reads the description of a set of vertical segments,  
  
computes the number of triangles in this set,  
  
writes the result.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.  
  
The first line of each data set contains exactly one integer n, 1 <= n <= 8 000, equal to the number of vertical line segments.  
  
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:  
  
yi', yi'', xi - y-coordinate of the beginning of a segment, y-coordinate of its end and its x-coordinate, respectively. The coordinates satisfy 0 <= yi' < yi'' <= 8 000, 0 <= xi <= 8 000. The segments are disjoint.

Output

The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.

Sample Input

1
    5
    0 4 4
    0 3 1
    3 4 2
    0 2 2
    0 2 3

Sample Output

题解：

先说题意：

给你一堆平行于y轴的线段的下端点y1，上端点y2，和横坐标x，让你求有多少对3个"两两可见"的线段，所谓两两可见就是两条线段可以被同一根水平线穿过而且之间不穿过其他线

思路：

由于题目意思一开始就不太明白之间就搜了题解，所以不是自己想的。。只说一下我的理解

由于处于同一个x的两个相邻线段也是互相可见，我们将线段的纵坐标都乘上2来处理线段覆盖问题，然后就是将线段按照x轴从小到大排序，然后先询问区间，询问结果用一个二维数组再保存，然后再插入更新，最后暴力三重循环来求个数。

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    struct node
    {
        int l,r;
        int v;//存之前被那条线覆盖
    }t[16000*4];
    bool p[8005][8005];//存可见情况
    void Build(int l,int r,int k)
    {
        t[k].v=-1;//初始-1
        t[k].l=l;
        t[k].r=r;
        if(l==r)
            return;
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void pushdown(int k)//向下更新
    {
        if(t[k].v!=-1)
        {
            t[lson].v=t[rson].v=t[k].v;
            t[k].v=-1;
        }
    }
    void update(int l,int r,int k,int v)区间更新
    {
        if(t[k].l==l&&t[k].r==r)
        {
            t[k].v=v;
            return;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            update(l,r,lson,v);
        else if(l>mid)
            update(l,r,rson,v);
        else
        {
            update(l,mid,lson,v);
            update(mid+1,r,rson,v);
        }
    }
    void query(int l,int r,int k,int v)//变相询问
    {
        if(t[k].v!=-1)//如果有线段覆盖了该段
        {
            p[t[k].v][v]=true;//注意是单向的，因为一对只算一次
            return;
        }
        if(t[k].l==t[k].r)
            return;
        pushdown(k);
        int mid=M;
        if(r<=mid)
            query(l,r,lson,v);
        else if(l>mid)
            query(l,r,rson,v);
        else
        {
            query(l,mid,lson,v);
            query(mid+1,r,rson,v);
        }
    }
    struct edge
    {
        int x,y1,y2;
    }a[8005];
    int cmp(edge a,edge b)//按照x来排序
    {
        return a.x<b.x;
    }
    int main()
    {
        int i,j,k,n,m,test,ans;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d",&n);
            Build(0,16000,1);
            memset(p,0,sizeof(p));
            for(i=0;i<n;i++)
            {
                scanf("%d%d%d",&a[i].y1,&a[i].y2,&a[i].x);
                a[i].y1*=2;
                a[i].y2*=2;//乘上2处理
            }
            sort(a,a+n,cmp);//排序
            for(i=0;i<n;i++)
            {
                query(a[i].y1,a[i].y2,1,i);
                update(a[i].y1,a[i].y2,1,i);
            }
            ans=0;
            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    if(p[i][j])//如果可见
                    {
                        for(k=0;k<n;k++)
                        {
                            if(p[i][k]&&p[j][k])
                            {
                                ans++;
                            }
                        }
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }