HDU 5862 Counting Intersections(离散化+树状数组)

题目链接http://acm.split.hdu.edu.cn/showproblem.php?pid=5862

Description

Input

Output

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

题意：

题解：

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 101000;

#define lowbit(x) (x&(-x))

struct Node{

    int type,x,y,y1;

    bool operator < (const Node & R)const{

        return (x == R.x ? type < R.type : x < R.x);

    }

}node[maxn*2];

int Maxn;

int cy[maxn*2];

int bi[maxn*2];

void add(int add,int n){

    for (int i = add; i <= Maxn; i += lowbit(i))

        bi[i] += n;

}

int sum(int n){

    int ret = 0;

    for (int i = n; i > 0; i -= lowbit(i))

        ret += bi[i];

    return ret;

}

map <int,int>mp;

int main()

{

    int t;

    scanf("%d",&t);

    while (t--){

        mp.clear();

        memset(bi,0,sizeof bi);

        int n;

        scanf("%d",&n);

        int cnode,ccy;

        cnode = ccy = 0;

        int x1,x2,y1,y2;

        for (int i = 1; i <= n; i++){

            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

            if (x1 == x2){

                if (y1 > y2)    swap(y1,y2);

                node[++cnode]={1,x1,y1,y2};

                cy[++ccy] = y1;

                cy[++ccy] = y2;

            }else {

                if (x1 > x2)    swap(x1,x2);

                node[++cnode]={0,x1,y1,1};

                node[++cnode]={0,x2+1,y2,-1};

                cy[++ccy] = y1;

            }

        }

        sort(cy+1,cy+ccy+1);

        int acl = 0;

        for (int i = 1; i <= ccy; i++){

            if (!mp[cy[i]]) mp[cy[i]] = ++ acl;

        }

        Maxn = acl;

        sort(node+1,node+cnode+1);

        long long ans = 0;

        for (int i = 1; i <= cnode; i++){

            if (node[i].type){

                ans += (sum(mp[node[i].y1]) - sum(mp[node[i].y]-1));

            }else {

                add(mp[node[i].y],node[i].y1);

            }

        }

        printf("%lld\n",ans);

    }

    return 0;

}