1. 首页
  2. 文章中心
  3. Other

2019杭电多校第⑨场B Rikka with Cake (主席树，离散化)

154 阅读 0 评论
我是靠谱客的博主 辛勤枕头，这篇文章主要介绍2019杭电多校第⑨场B Rikka with Cake (主席树，离散化)，现在分享给大家，希望可以做个参考。

题意：

给定一块n*m的矩形区域，在区域内有若干点，每个顶点发出一条射线，有上下左右四个方向，问矩形被分成了几个区域？

思路：

稍加观察和枚举可以发现，区域数量=射线交点数+1(可以用欧拉定理验证，但是我不会)，问题就转变为统计射线交点数量

可以将四个方向的射线分开，用左右的射线去查询与多少个上下的射线相交，先考虑向左的射线A与几条向上的射线相交，设A(x,y)，即求(1,x)区间内(le y)的向上的射线条数，显然可以利用主席树进行维护(也可以用树状数组并且更快，但是我不会)。其他情况同理，注意离散化时向上靠近还是向下靠近

由于y是在(1,1e9)范围内的，因此y需要离散化，因为主席树的性质，x必须排序离散化

复制代码
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
//memory= 1.3e8 int
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
const int N=1e5+2;
int xu[maxn],xd[maxn],val[maxn];
int x1[maxn],y1[maxn];
char c1[maxn];
const int Log=50;
int root[2][maxn],num[2][maxn*Log],lson[2][maxn*Log],rson[2][maxn*Log];
int tot[2];
double Sum,Num;
int build(int id,int l,int r){
    int root=++tot[id];
    num[id][root]=0;
    if(l<r){
        int mid=(l+r)>>1;
        lson[id][root]=build(id,l,mid);
        rson[id][root]=build(id,mid+1,r);
    }
    return root;
}
int update(int id,int pre,int l,int r,int x){
    int root=++tot[id];
    num[id][root]=num[id][pre]+1;
    lson[id][root]=lson[id][pre];
    rson[id][root]=rson[id][pre];
    if(l<r){
        int mid=(l+r)>>1;
        if(x<=mid) lson[id][root]=update(id,lson[id][pre],l,mid,x);
        else rson[id][root]=update(id,rson[id][pre],mid+1,r,x);
    }
    return root;
}
int query(int id,int Old,int New,int l,int r,int k){//Old和New对应旧版本的根和新版本的根
    if(id==0){//向上，查区间内<=k的数的个数 
        if(r<=k){
            return num[id][New]-num[id][Old];
        }
        int mid=(l+r)>>1;
        int res=0;
        if(l<=k) res+=query(id,lson[id][Old],lson[id][New],l,mid,k);
        if(mid+1<=k) res+=query(id,rson[id][Old],rson[id][New],mid+1,r,k);
        return res;
    }
    else{//向下，查区间内>=k的数的个数
        if(l>=k){
            return num[id][New]-num[id][Old];
        }
        int mid=(l+r)>>1;
        int res=0;
        if(mid>=k) res+=query(id,lson[id][Old],lson[id][New],l,mid,k);
        if(r>=k) res+=query(id,rson[id][Old],rson[id][New],mid+1,r,k);
        return res;
    }
}
struct node{
    node(int a,int b):x(a),y(b){}
    int x,y;
};
bool cmp(node a,node b){
    return a.x<b.x;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        tot[0]=tot[1]=0;
        int n,m,k;
        vector<node> U,D,R,L;
        scanf("%d%d%d",&n,&m,&k);
        int x,y;
        char c;
        int sizexu=0,sizexd=0,sizey=0;
        for(int i=1;i<=k;i++){
            scanf("%d%d %c",&x,&y,&c);
            x1[i]=x;y1[i]=y;c1[i]=c;
            if(c=='U') xu[++sizexu]=x;
            if(c=='D') xd[++sizexd]=x;
            val[++sizey]=y;
        }
        sort(xu+1,xu+1+sizexu);
        sort(xd+1,xd+1+sizexd);
        sort(val+1,val+1+sizey);
        sizexu=unique(xu+1,xu+1+sizexu)-(xu+1);
        sizexd=unique(xd+1,xd+1+sizexd)-(xd+1);
        sizey=unique(val+1,val+1+sizey)-(val+1);
        for(int i=1;i<=k;i++){//U,D中存离散化的坐标值。L,R存原值，之后再在对应数组中二分找离散值
            if(c1[i]=='U'){
                x1[i]=lower_bound(xu+1,xu+1+sizexu,x1[i])-xu;
                y1[i]=lower_bound(val+1,val+1+sizey,y1[i])-val;
                U.push_back(node(x1[i],y1[i]) );
            }
            if(c1[i]=='D'){
                x1[i]=lower_bound(xd+1,xd+1+sizexd,x1[i])-xd;
                y1[i]=lower_bound(val+1,val+1+sizey,y1[i])-val;
                D.push_back(node(x1[i],y1[i]) );
            }
            if(c1[i]=='L') L.push_back(node(x1[i],y1[i]) );
            if(c1[i]=='R') R.push_back(node(x1[i],y1[i]) );
        }
        //建2棵主席树，分别存U，D，再用L和R取查找
        root[0][0]=build(0,1,N);
        root[1][0]=build(1,1,N);
        sort(U.begin(),U.end(),cmp);
        for(int i=0;i<U.size();i++)
            root[0][i+1]=update(0,root[0][i],1,N,U[i].y);
        sort(D.begin(),D.end(),cmp);
        for(int i=0;i<D.size();i++)
            root[1][i+1]=update(1,root[1][i],1,N,D[i].y);
        int ans=0;
        for(int i=0;i<L.size();i++){
            int r0=upper_bound(xu+1,xu+1+sizexu,L[i].x)-xu-1;//找<=，向左靠近
            int r1=upper_bound(xd+1,xd+1+sizexd,L[i].x)-xd-1;//找<=，向左靠近
            int h=lower_bound(val+1,val+1+sizey,L[i].y)-val;
            ans+=query(0,root[0][0],root[0][r0],1,N,h);
            ans+=query(1,root[1][0],root[1][r1],1,N,h);
        }
        for(int i=0;i<R.size();i++){
            int l0=lower_bound(xu+1,xu+1+sizexu,R[i].x)-xu;//找>=，向右靠近
            int l1=lower_bound(xd+1,xd+1+sizexd,R[i].x)-xd;//找>=，向右靠近
            int h=lower_bound(val+1,val+1+sizey,R[i].y)-val;
            ans+=query(0,root[0][l0-1],root[0][U.size()],1,N,h);
            ans+=query(1,root[1][l1-1],root[1][D.size()],1,N,h);
        }
        printf("%dn",ans+1);
    }
}

转载于:https://www.cnblogs.com/ucprer/p/11388097.html

最后

以上就是辛勤枕头最近收集整理的关于2019杭电多校第⑨场B Rikka with Cake (主席树，离散化)的全部内容，更多相关2019杭电多校第⑨场B内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(102)

相关文章

HDU6681-Rikka with Cake（转化为线段树模型）
HDU6681-Rikka with Cake（转化为线段树模型）
A - A + B Problem II
A - A + B Problem II
HDU 6681（树状数组统计平面内射线的交点个数）HDU 6681（树状数组，统计平面内射线的交点个数）
HDU 6681（树状数组统计平面内射线的交点个数）HDU 6681（树状数组，统计平面内射线的交点个数）
HDU - 6681
HDU - 6681
2019杭电多校第⑨场B Rikka with Cake (主席树，离散化)
2019杭电多校第⑨场B Rikka with Cake (主席树，离散化)
2019杭电暑期多校第九场 B：Rikka with Cake（离散化+树状数组）
2019杭电暑期多校第九场 B：Rikka with Cake（离散化+树状数组）
2019HDU多校 Round9
2019HDU多校 Round9
2019杭电多校第二场6009（树状数组）
2019杭电多校第二场6009（树状数组）

评论列表共有 0 条评论

立即
投稿
返回
顶部