HDU 6681（树状数组统计平面内射线的交点个数）HDU 6681（树状数组，统计平面内射线的交点个数）

116 阅读 0 评论 77 点赞

我是靠谱客的博主快乐缘分，这篇文章主要介绍HDU 6681（树状数组统计平面内射线的交点个数）HDU 6681（树状数组，统计平面内射线的交点个数），现在分享给大家，希望可以做个参考。

HDU 6681（树状数组，统计平面内射线的交点个数）

题目链接：传送门

题意：给出k条射线，求射线将 $n * m$ 的区域分成几个联通块。每两条射线的端点x坐标和y坐标都互不相同。

思路：根据 欧拉公式 可以推导出联通块的个数等于射线的焦点个数c+1。但其实赛场上根本不知道这个定理，但有个很明显的道理，对于每条竖线，每条横着的射线与该竖线相交都会使联通块个数+1.(注意因为题目限制，这个射线的端点不会在边界上，不然在边界的射线会使联通块+2)。所以我们直接统计出射线的交点个数即可，这是个经典问题（但是我当时不会

其实对于每条竖着的射线(假设端点为 $x 0, y 0 $ )，只要能统计出它左边横着的射线与之相交的射线个数和，即相交的射线的端点 $x, y $ 满足射线方向向右且 $x < x 0 $ ，y在射线( $x 0, y 0 $ )纵坐标覆盖范围之内即可。统计左边横着的射线与之相交的射线个数也是同样道理

因为射线的个数 $k$ 的范围为 $1 e 5 $ ，故使用二维前缀和肯定是不行的。

我们可以分类统计，我们先来统计每条射线左边横着的射线与之相交的射线个数，我们可以先将所有竖直方向的射线按 $x$ 从小到大排序，所有横着的射线按 $x$ 从小到大排序，对于第 $i$ 条竖直方向的射线，我们可以处理所有左边的横着向右的射线，然后把他们的 $y$ 坐标加入树状数组 (这里需要对 $y$ 坐标进行离散化)。然后可以 $O (l o g n)$ 统计出树状数组内 $y$ 在第一条射线纵坐标覆盖范围之内的点的个数。双指针优化后可达到O(n)统计的效果。

欧拉公式：欧拉公式介绍

代码：

复制代码

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int N=1e5+100;
const int L=0,R=1,U=2,D=3;
ll X[N],Y[N],kinds[N],n,m,K,pes[N];
ll bt[N];
ll maxm;
struct node
{
    ll x,y,kind;
    node() {}
    node(ll x,ll y,ll kind):x(x),y(y),kind(kind) {}

bool operator <(const node& other) const
    {
        return x<other.x;
    }
};
vector<node> row,col;
void disperse(ll X[],ll n)
{
    ll cnt=0;
    for(ll i=1; i<=n; ++i)
        pes[cnt++]=X[i];
    sort(pes,pes+cnt);
    cnt=unique(pes,pes+cnt)-pes;
    for(ll i=1; i<=n; ++i)
    {
        X[i]=lower_bound(pes,pes+cnt,X[i])-pes+1;
    }
}
ll lowbit(ll k)
{
    return k&-k;
}
void add(ll k,ll val)
{
    while(k<=maxm)
    {
        bt[k]+=val;
        k+=lowbit(k);
    }
}
ll get(ll k)
{
    ll ans=0;
    while(k)
    {
        ans+=bt[k];
        k-=lowbit(k);
    }
    return ans;
}
ll calc(ll l,ll r)
{
    return get(r)-get(l-1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>K;
        for(ll i=1; i<=K; ++i)
        {
            char c;
            cin>>X[i]>>Y[i]>>c;
            switch (c)
            {
            case 'L':
                kinds[i]=L;
                break;
            case 'R':
                kinds[i]=R;
                break;
            case 'U':
                kinds[i]=U;
                break;
            case 'D':
                kinds[i]=D;
                break;
            }
        }
        Y[K+1]=m;
        //离散化
        disperse(Y,K+1);
        maxm=Y[K+1];
        row.clear(),col.clear();
        //加入行列数组
        for(ll i=1; i<=K; ++i)
        {
            if(kinds[i]==L||kinds[i]==R)
            {
                row.push_back({X[i],Y[i],kinds[i]});
            }
            else
            {
                col.push_back({X[i],Y[i],kinds[i]});
            }
        }
        sort(row.begin(),row.end());
        sort(col.begin(),col.end());
        mset(bt,0);
        int p=0;
        ll ans=0;
        //进行双指针并树状数组维护信息
        /*统计每条竖线与左侧射线的交点个数*/
        for(ll i=0ll; i<col.size(); ++i)
        {
            ll x=col[i].x,y=col[i].y;
            while(p<row.size()&&row[p].x<x)
            {
                if(row[p].kind==R)
                    add(row[p].y,1);
                ++p;
            }
            if(col[i].kind==U)
                ans+=calc(y,maxm);
            else
                ans+=calc(1,y);
        }
        /*统计每条竖线与右侧射线的交点个数*/
        mset(bt,0);
        p=row.size()-1;
        for(ll i=col.size()-1ll; ~i; --i)
        {

ll x=col[i].x,y=col[i].y;
            while(p>=0&&row[p].x>x)
            {
                if(row[p].kind==L)
                    add(row[p].y,1);
                --p;
            }

if(col[i].kind==U)
                ans+=calc(y,maxm);
            else
                ans+=calc(1,y);
        }
        cout<<ans+1<<endl;
    }
    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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int N=1e5+100;
const int L=0,R=1,U=2,D=3;
ll X[N],Y[N],kinds[N],n,m,K,pes[N];
ll bt[N];
ll maxm;
struct node
{
    ll x,y,kind;
    node() {}
    node(ll x,ll y,ll kind):x(x),y(y),kind(kind) {}


    bool operator <(const node& other) const
    {
        return x<other.x;
    }
};
vector<node> row,col;
void disperse(ll X[],ll n)
{
    ll cnt=0;
    for(ll i=1; i<=n; ++i)
        pes[cnt++]=X[i];
    sort(pes,pes+cnt);
    cnt=unique(pes,pes+cnt)-pes;
    for(ll i=1; i<=n; ++i)
    {
        X[i]=lower_bound(pes,pes+cnt,X[i])-pes+1;
    }
}
ll lowbit(ll k)
{
    return k&-k;
}
void add(ll k,ll val)
{
    while(k<=maxm)
    {
        bt[k]+=val;
        k+=lowbit(k);
    }
}
ll get(ll k)
{
    ll ans=0;
    while(k)
    {
        ans+=bt[k];
        k-=lowbit(k);
    }
    return ans;
}
ll calc(ll l,ll r)
{
    return get(r)-get(l-1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>K;
        for(ll i=1; i<=K; ++i)
        {
            char c;
            cin>>X[i]>>Y[i]>>c;
            switch (c)
            {
            case 'L':
                kinds[i]=L;
                break;
            case 'R':
                kinds[i]=R;
                break;
            case 'U':
                kinds[i]=U;
                break;
            case 'D':
                kinds[i]=D;
                break;
            }
        }
        Y[K+1]=m;
        //离散化
        disperse(Y,K+1);
        maxm=Y[K+1];
        row.clear(),col.clear();
        //加入行列数组
        for(ll i=1; i<=K; ++i)
        {
            if(kinds[i]==L||kinds[i]==R)
            {
                row.push_back({X[i],Y[i],kinds[i]});
            }
            else
            {
                col.push_back({X[i],Y[i],kinds[i]});
            }
        }
        sort(row.begin(),row.end());
        sort(col.begin(),col.end());
        mset(bt,0);
        int p=0;
        ll ans=0;
        //进行双指针并树状数组维护信息
        /*统计每条竖线与左侧射线的交点个数*/
        for(ll i=0ll; i<col.size(); ++i)
        {
            ll x=col[i].x,y=col[i].y;
            while(p<row.size()&&row[p].x<x)
            {
                if(row[p].kind==R)
                    add(row[p].y,1);
                ++p;
            }
            if(col[i].kind==U)
                ans+=calc(y,maxm);
            else
                ans+=calc(1,y);
        }
        /*统计每条竖线与右侧射线的交点个数*/
        mset(bt,0);
        p=row.size()-1;
        for(ll i=col.size()-1ll; ~i; --i)
        {

            ll x=col[i].x,y=col[i].y;
            while(p>=0&&row[p].x>x)
            {
                if(row[p].kind==L)
                    add(row[p].y,1);
                --p;
            }

            if(col[i].kind==U)
                ans+=calc(y,maxm);
            else
                ans+=calc(1,y);
        }
        cout<<ans+1<<endl;
    }
    return 0;
}