POJ 1436 Horizontally VisibleSegments(线段树成段更新+区间覆盖染色)

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? 


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

1

  给出N(N <= 8000)条垂直线段，如果两条线段在水平方向上连一条线之后不和其他任何垂直线段相交，那么我们称这两条线段水平可见，如果三条垂直线段两两水平可见，则称其为一个三角，问着N条线段能组成多少三角。

首先如果我们可以求得任意两条垂直线段i和j之间是否可见mark[i][j]，那么我们可以用暴力O(n^3)遍历的方式来得到所有三角个数。所以下面我们只要求出这个mark矩阵即可。本题就变成了一个线段树区间覆盖染色问题了。

首先读入所有的线段,然后按x轴坐标从小到大排序,然后我们一次处理每条线段,用一个二维矩阵mark[i][j]保存第i条线段和第j条线段之间的关系.(如果相互可以看到,则mark为true,否则为false).

下面的问题是如果求出任意两线段之间的可见关系呢?把线段按x坐标排序,如果第4条线段和第7条线段可见:含义是已经放好了第5条和第6条线段第7条线段依然能看到第4条.所以我们只需要求出第i条线段与前i-1条线段的可见关系即可.

线段树维护color信息,color>0时,表示节点已经被某个线段覆盖,color=0表示节点没有被任何线段覆盖,color=-1,表示节点被多种情况覆盖(其子节点可能被多个线段分别覆盖,或者有些根本没覆盖).每加入一条新线段,我们先查询它能看到的color,然后更新节点覆盖情况.

如果有4条线段区间依次(依x从小到大的次序)分别为[2,3][1,2],[3,4]和[1,4],那么[1,4]能看到的线段应该是3条,但是如果我们按照上面的做法[1,4]就只能看到两条线,因为开区间(2,3)未被考虑.所以为了考虑开区间,我们把所有的节点的y坐标加倍(由于老的区间是[0,8000],新的区间节点为0-16000,程序为了保险设为16000+2),即以前的区间[1,1]用[2,2]表示,[2,2]用[4,4]表示,所以新的3用来表示开区间(1,2).

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;
const int maxn = 20000;

struct Segment_Tree
{
    #define lson l, mid, rt << 1
    #define rson mid + 1, r, rt << 1 | 1
    int color[maxn << 2];
    bool cansee[maxn/2][maxn/2];
    void pushUp(int rt)
    {
        if(color[rt << 1] == color[rt << 1 | 1] && color[rt << 1] != -1)
            color[rt] = color[rt << 1];
        else color[rt] = -1;
    }
    void pushDown(int rt)
    {
        if(color[rt] != -1)
        {
            color[rt << 1] = color[rt << 1 | 1] = color[rt];
            color[rt] = -1;
        }
    }
    void update(int l, int r, int rt, int L, int R, int value)
    {
        if(l >= L && r <= R)
        {
            color[rt] = value;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(rt);
        if(mid >= L) update(lson, L, R, value);
        if(mid + 1 <= R) update(rson, L, R, value);
        pushUp(rt);
    }
    void query(int l, int r, int rt, int L, int R, int value)
    {
        if(l >= L && r <= R)
        {
            if(color[rt] != -1)
            {
                if(color[rt])
                    cansee[color[rt]][value] = cansee[value][color[rt]] = 1;
                return;
            }
        }
        int mid = (l + r) >> 1;
        pushDown(rt);
        if(mid >= L) query(lson, L, R, value);
        if(mid + 1 <= R) query(rson, L, R, value);
        pushUp(rt);
    }
};

Segment_Tree ST;

struct Segment
{
    int x, y1, y2;
    Segment(int _x, int _y1, int _y2)
    {
        x = _x, y1 = _y1, y2 = _y2;
    }
    Segment(){}
};

bool cmp(Segment s1, Segment s2)
{
    return s1.x < s2.x;
}

Segment s[8080];

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        int y1, y2, x;
        int ma = -1;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d %d %d", &y1, &y2, &x);
            if(y1 > y2) swap(y1, y2);
            s[i] = Segment(x, y1*2, y2*2);
            ma = max(ma, y2*2);
        }
        sort(s + 1, s + n + 1, cmp);
        ST.color[1] = 0;
        memset(ST.cansee, 0, sizeof(ST.cansee));
        for(int i = 1; i <= n; i++)
        {
            ST.query(0, ma, 1, s[i].y1, s[i].y2, i);
            ST.update(0, ma, 1, s[i].y1, s[i].y2, i);

        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
            for(int j = i + 1; j <= n; j++)
                if(ST.cansee[i][j])
                    for(int k = j + 1; k <= n; k++)
                        if(ST.cansee[i][k] && ST.cansee[j][k])
                            ans++;
        printf("%d\n", ans);
    }
    return 0;
}