HDU 5862 Counting Intersections（离散化 + 树状数组）Counting Intersections

Counting Intersections

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1138    Accepted Submission(s): 347

Problem 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

Author

BUPT

Source

2016 Multi-University Training Contest 10

 【分析】给你一些与坐标轴平行的线段，问有多少对线段相交。

  对于这种N*N可以办到但是超时的统计问题，一般都树状数组来统计。先将坐标离散化，然后横向线段存两个端点的横坐标，纵向的存一个横   坐标，然后排序，统计。若遇到一条横向线段的左端点，则纵坐标向上lowbit加一，若遇到纵向线段，统计这条线段的累加值，若遇到横向线     段的右端点，纵坐标向上lowbit减一，即删除，因为它已经没有贡献了。

  

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define met(a,b) memset(a,b,sizeof a)
#define inf 10000000
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N = 4e5+5;
const double eps = 1e-8;
int n,sum[N],m,cnt;
ll ans;
int lazy[N],a[N],mi[N],ma[N];
struct Line{
    int u,y,z;
    Line(int u=0,int y=0,int z=0):u(u),y(y),z(z){}
    bool operator <(const Line f)const{
        return u<f.u||u==f.u&&z<f.z;
    }
};
vector<Line>r,c,q;
void init(){
    cnt=ans=0;
    met(a,0);
    r.clear();c.clear();q.clear();
}
void add(int x,int num){
    for(int i=x;i<N;i+=i&(-i)){
        a[i]+=num;
    }
}
int query(int x){
    int ret=0;
    for(int i=x;i>=1;i-=i&(-i)){
        ret+=a[i];
    }
    return ret;
}
int main() {
    int T,x,y,xx,yy;
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&x,&y,&xx,&yy);
            mi[++cnt]=x;mi[++cnt]=xx;
            mi[++cnt]=y;mi[++cnt]=yy;
            if(x==xx){
                if(y>yy)swap(y,yy);
                c.pb(Line(x,y,yy));
            }
            if(y==yy){
                if(x>xx)swap(x,xx);
                r.pb(Line(y,x,xx));
            }
        }
        sort(mi+1,mi+1+cnt);
        cnt=unique(mi+1,mi+1+cnt)-mi-1;
        for(int i=0;i<c.size();i++){
            c[i].u=lower_bound(mi+1,mi+1+cnt,c[i].u)-mi;
            c[i].y=lower_bound(mi+1,mi+1+cnt,c[i].y)-mi;
            c[i].z=lower_bound(mi+1,mi+1+cnt,c[i].z)-mi;
            q.pb(Line(c[i].u,i,2));
        }
        for(int i=0;i<r.size();i++){
            r[i].u=lower_bound(mi+1,mi+1+cnt,r[i].u)-mi;
            r[i].y=lower_bound(mi+1,mi+1+cnt,r[i].y)-mi;
            r[i].z=lower_bound(mi+1,mi+1+cnt,r[i].z)-mi;
            q.pb(Line(r[i].y,i,1));
            q.pb(Line(r[i].z,i,3));
        }
        sort(q.begin(),q.end());
        for(Line s:q){
            if(s.z==1)add(r[s.y].u,1);
            else if(s.z==2)ans+=query(c[s.y].z)-query(c[s.y].y-1);
            else add(r[s.y].u,-1);
        }
        printf("%lldn",ans);
    }
    return 0;
}