codeforcesPoints - CheaSim Blog

codeforcesPoints

codeforcesPoints

题意

给出几个点,让你求出在某个点的右边和上面最接近他的点是哪一个点。

题解

线段树+set应用

对$x$进行离散化处理,对于每一个$x$进行建一个set,用线段树维护$x$之间的$y$的最大值。对于给出点的右上点,我们可以用二分来set搜索,还有在线段树中优先搜索左边靠近给出点的点。

这是我第一次看到离散化的线段树应用。哭泣

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
inline int Max(int a,int b){return a>b?a:b;}
//head
const int maxn = 2e5 + 20;
int maxy[maxn<<2],mark[maxn],x[maxn],y[maxn];
set<int> s[maxn];
int n,m;
char op[20];
vector<int> v;
void build(int l,int r,int rt){
if(l==r){
maxy[rt] = -1;
return;
}else{
int mid = (l+r)>>1;
build(lson);
build(rson);
}
}
void pushup(int rt){
maxy[rt] = Max(maxy[rt<<1],maxy[rt<<1|1]);
}
void update(int pos,int val,int l,int r,int rt){
if(l==r){
maxy[rt] = val;
return;
}
int mid = (l+r)>>1;
if(pos <= mid) update(pos,val,lson);
else update(pos,val,rson);
pushup(rt);
}
int query(int L,int R,int val,int l,int r,int rt){
if(maxy[rt] <= val) return -1;
if(l==r) return l;
int mid = (l+r)>>1;
int ans = -1;
if(L <= mid && maxy[rt<<1] > val){
ans = query(L,R,val,lson);
if(ans != -1) return ans;
}
if(R > mid && maxy[rt<<1|1] > val)
ans = query(L,R,val,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("points.in","r",stdin);
#endif
scanf("%d",&n);
rep(i,0,n){
scanf("%s%d%d",op,&x[i],&y[i]);
if(op[0] == 'a') mark[i] = 1;
else if(op[0] == 'r') mark[i] = 2;
else mark[i] = 3;
if(op[0] == 'a') v.push_back(x[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
m = v.size();
rep(i,0,n){
if(mark[i] == 1 || mark[i] == 2){
int pos = lower_bound(v.begin(),v.end(),x[i]) - v.begin()+1;
if(mark[i] == 1) s[pos].insert(y[i]);
else s[pos].erase(y[i]);
int val;
if(s[pos].empty()) val = -INF;
else val = *(--s[pos].end());
update(pos,val,1,m,1);
}else{
int pos = upper_bound(v.begin(),v.end(),x[i]) - v.begin()+1;
int z = query(pos,m,y[i],1,m,1);
if(z == -1 || pos == m+1){
puts("-1"); continue;
}
int ans = *(s[z].upper_bound(y[i]));
printf("%d %d\n",v[z-1],ans);
}
}
return 0;
}
作者

CheaSim

发布于

2018-08-18

更新于

2018-08-18

许可协议

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论