HDU5862 Counting Intersections

2016多校, HDU, 树状数组

　　2016 Multi-University Training Contest 10

　　题意：给定n条垂直于坐标轴的线段，求交点个数。 - 原题链接

　　题目中线段被限制为垂直或水平。将线段坐标离散化后，按纵坐标从小到大扫描。遇到垂直线段的下端点，则插入该线段的横坐标值；遇到水平线段，则查询x1[i]到x2[i]的区间和；遇到垂直线段的上端点，则删除该线段的横坐标值。线段树、树状数组均可以维护。
　　需要注意的是纵坐标相同时，三种操作的顺序不能变。第一次的代码开了三个vector来记录三种操作序列，结果MLE… 后来改了一下，只用一个vector来记录相同纵坐标的点，每种操作赋优先级0、1、2，在处理每一个vector时先进行内部排序，2418MS AC。两份代码均在下方给出。 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//AC代码
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define lowbit(x) ((x)&-(x))
using namespace std;
const int maxn=1e6 + 10;
typedef long long lint;
int T, n, N, M, a[maxn<<1], b[maxn<<1], s[maxn<<1];
struct line
{
    int x1, y1, x2, y2, d;
    line(int xx1=0, int yy1=0, int xx2=0, int yy2=0) { x1=xx1, y1=yy1, x2=xx2, y2=yy2; }
    void read()
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if(x1>x2)    swap(x1, x2);
        if(y1>y2)    swap(y1, y2);
        a[++N]=x1, a[++N]=x2, b[++M]=y1, b[++M]=y2;
        return ;
    }
    void hash()
    {
        x1=lower_bound(a+1, a+1+N, x1)-a, x2=lower_bound(a+1, a+1+N, x2)-a;
        y1=lower_bound(b+1, b+1+M, y1)-b, y2=lower_bound(b+1, b+1+M, y2)-b;
        return ;
    }
}seg[maxn];
struct node
{
    int d, idx;
    node(int dd=0, int idxx=0) { d=dd, idx=idxx; }
    bool operator <(const node&t)const { return d<t.d; }
};
vector<node> vct[maxn];
void Add(int x, int val)
{
    for(int i=x; i<=N; i+=lowbit(i))    s[i]+=val;
    return ;
}
int Query(int x, int ans=0)
{
    for(int i=x; i; i-=lowbit(i))    ans+=s[i];
    return ans;
}
void Clear()
{
    for(int i=0; i<=M; i++)    vct[i].clear();
    memset(s, 0, sizeof s);
    N=M=0;
    return ;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)    seg[i].read();
        sort(a+1, a+1+N);
        sort(b+1, b+1+M);
        N=unique(a+1, a+1+N)-a-1;
        M=unique(b+1, b+1+M)-b-1;
        for(int i=1; i<=n; i++)    seg[i].hash();
        for(int i=1; i<=n; i++)
        {
            if(seg[i].y1==seg[i].y2)    vct[seg[i].y1].push_back(node(1, i));
            else vct[seg[i].y1].push_back(node(0, i)), vct[seg[i].y2].push_back(node(2, i));
        }
        lint ans=0;
        for(int i=1; i<=M; i++)
        {
            sort(vct[i].begin(), vct[i].end());
            for(int j=0, len=vct[i].size(); j<len; j++)
            {
                if(vct[i][j].d==0)    Add(seg[vct[i][j].idx].x1, 1);
                else if(vct[i][j].d==2)    Add(seg[vct[i][j].idx].x1, -1);
                else ans+=Query(seg[vct[i][j].idx].x2)-Query(seg[vct[i][j].idx].x1-1);
            }
        }
        cout<<ans<<endl;
        Clear();
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//MLE代码
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define lowbit(x) ((x)&-(x))
using namespace std;
const int maxn=1e6 + 10;
typedef long long lint;
int T, n, N, M, a[maxn<<1], b[maxn<<1], s[maxn<<1];
vector<int> vct1[maxn<<1], vct2[maxn<<1], vct3[maxn<<1];
struct line
{
    int x1, y1, x2, y2, d;
    line(int xx1=0, int yy1=0, int xx2=0, int yy2=0) { x1=xx1, y1=yy1, x2=xx2, y2=yy2; }
    void read()
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if(x1>x2)    swap(x1, x2);
        if(y1>y2)    swap(y1, y2);
        a[++N]=x1, a[++N]=x2, b[++M]=y1, b[++M]=y2;
        return ;
    }
    void hash()
    {
        x1=lower_bound(a+1, a+1+N, x1)-a, x2=lower_bound(a+1, a+1+N, x2)-a;
        y1=lower_bound(b+1, b+1+M, y1)-b, y2=lower_bound(b+1, b+1+M, y2)-b;
        return ;
    }
}seg[maxn];
void Add(int x, int val)
{
    for(int i=x; i<=N; i+=lowbit(i))    s[i]+=val;
    return ;
}
int Query(int x, int ans=0)
{
    for(int i=x; i; i-=lowbit(i))    ans+=s[i];
    return ans;
}
void Clear()
{
    for(int i=0; i<=M; i++)    vct1[i].clear(), vct2[i].clear(), vct3[i].clear();
    memset(s, 0, sizeof s);
    N=M=0;
    return ;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)    seg[i].read();
        sort(a+1, a+1+N);
        sort(b+1, b+1+M);
        N=unique(a+1, a+1+N)-a-1;
        M=unique(b+1, b+1+M)-b-1;
        for(int i=1; i<=n; i++)    seg[i].hash();
        for(int i=1; i<=n; i++)
        {
            if(seg[i].y1==seg[i].y2)    vct1[seg[i].y1].push_back(i);
            else vct2[seg[i].y1].push_back(i), vct3[seg[i].y2].push_back(i);
        }
        lint ans=0;
        for(int i=1; i<=M; i++)
        {
            for(int j=0, len=vct2[i].size(); j<len; j++)    Add(seg[vct2[i][j]].x1, 1);
            for(int j=0, len=vct1[i].size(); j<len; j++)    ans+=Query(seg[vct1[i][j]].x2)-Query(seg[vct1[i][j]].x1-1);
            for(int j=0, len=vct3[i].size(); j<len; j++)    Add(seg[vct3[i][j]].x1, -1);
        }
        cout<<ans<<endl;
        Clear();
    }
    return 0;
}