HDU 5862 Counting Intersections （树状数组）

Counting Intersections

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5862

Description

Given some segments which are paralleled to the coordinate axis. You need to count the number of their intersection. The input data guarantee that no two segments share the same endpoint, no covered segments, and no segments with length 0.

Input

The first line contains an integer T, indicates the number of test case. The first line of each test case contains a number n(1<=n<=100000), the number of segments. Next n lines, each with for integers, x1, y1, x2, y2, means the two endpoints of a segment. The absolute value of the coordinate is no larger than 1e9.

Output

For each test case, output one line, the number of intersection.

Sample Input

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

Sample Output

4 0

Source

2016 Multi-University Training Contest 10
##题意：给出平面上N条平行于坐标轴的线段. 保证线段没有公共端点，没有覆盖. 求N条线段有多少个交点.
##题解：对于所有线段按照x坐标排序，将y坐标离散化，在从左到右遍历线段的过程中：遇到水平线段的左端点时，将其对应y坐标在树状数组中的值+1. 遇到水平线段的(右端点+1)时，将其对应y坐标在树状数组中的值-1. 遇到竖直线段时，查询其纵坐标区间的和，即为这条竖直线段能产生的交点的个数.
注意的几点：以下代码将水平线段当成两个点来存储，竖直线段当成一个点来存储. 离散化时只需要对y坐标离散. 在排序时，x坐标是第一优先级，其次应该按先水平再竖直排序. 这样可以保证'T'字型情况得到处理. 应该在遇到水平线段右端点+1的位置时才将树状数组中的值-1. 树状数组中的n为需要处理的纵坐标的个数，不是输入的n，务必区分开来.
比赛时想的是区间更新+单点查询，即先将在某条水平线段横坐标区间内竖直线段进行区间更新，这样一来对水平线段的排序就不太好处理，比如投影区间覆盖的情况. 贴一个[线段树+扫描线](http://www.cnblogs.com/zhangchengc919/p/5784725.html)的解法，过几天学习一下：
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 201000 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

struct node {
int type; // 0横 1竖
int x, y1,y2;
node() {}
node(int a,int b,int c,int d) {type=a;x=b;y1=c;y2=d;}
bool operator < (const node& b) const {
if(x == b.x) return type < b.type; //先处理横向
return x < b.x;
}
}p[maxn];

int n, cnt;

int c[maxn];

int lowbit(int x) {
return x & (-x);
}

int newn; // 区别于n
void update(int x, int d) {
while(x <=newn) {
c[x] += d;
x += lowbit(x);
}
}

int get_sum(int x) {
LL ret = 0;
while(x > 0) {
ret += c[x];
x -= lowbit(x);
}
return ret;
}

map<int, int> mp;
int pos[maxn], pos_cnt;

int main(int argc, char const *argv[])
{
//IN;

int t; cin >> t;
while(t--)
{
    scanf("%d", &n);
    mp.clear();
    cnt = 0; pos_cnt = 0;

    for(int i=1; i<=n; i++) {
        int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        if(y1 == y2) { // hor
            if(x1 > x2) swap(x1, x2);
            p[++cnt] = node(0, x1, y1, +1);
            p[++cnt] = node(0, x2+1, y1, -1); //右端点的下一个位置
            pos[++pos_cnt] = y1;
        } else { // ver
            if(y1 > y2) swap(y1, y2);
            p[++cnt] = node(1, x1, y1, y2);
            pos[++pos_cnt] = y1;
            pos[++pos_cnt] = y2;
        }
    }

    sort(pos+1, pos+1+pos_cnt);
    int counts = 0;
    for(int i=1; i<=pos_cnt; i++) {
        if(!mp[pos[i]]) mp[pos[i]] = ++counts;
    }

    sort(p+1, p+1+cnt);

    LL ans = 0;
    newn = counts; //务必与n区分开来
    memset(c, 0, sizeof(c));
    for(int i=1; i<=cnt; i++) {
        if(p[i].type == 0) { // hor
            update(mp[p[i].y1], p[i].y2);
        } else { // ver
            ans += get_sum(mp[p[i].y2]) - get_sum(mp[p[i].y1]-1);
        }
    }

    printf("%lld
", ans);
}

return 0;

}