题目链接
题目大意
你需要维护一个向量集合，支持以下三种操作：
(1) 插入一个新的向量
(2) 删除一个原有向量
(3) 给你一个向量a，查询目前向量集合中所有向量与a的点积的最大值
做法
博主对于计算几何一窍不通，看到这个想到了KDtree。
如果你要用KDtree做这题的话就非常简单，对于每个向量看成一个点，插入就KDtree中插入，删除也是。
对于询问操作，我们像查询平面最近点对一样，写一个估价函数，计算KDtree上每个点所包含的矩形与查询点的最大点积，显然就是这个矩形的右上点，即x最大，y最大。
其余的部分与查询平面最近点对无异。
虽然复杂度不对，但是由于出题人可能并没想到会有毒瘤像我一样写KDtree，所以数据没卡，凭借一个不带重构的KDtree跑到了全站第五，实测加了重构反而变慢。
写这篇博客可能只是想说有些题只要你有梦想，说不定暴力也能操标。
贴上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
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
using namespace std;
int n,op,x,y,tot,D,cnt,root,ax[N],ay[N];
int h[N],q[2];
LL ans;
double alpha=0.6;
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
struct node{
int l,r,d[2],mx[2],mn[2],knum,size;
bool kill;
}T[N];
inline bool cmp(int a,int b){
return T[a].d[D]<T[b].d[D];
}
inline void update(int x){
int l=T[x].l,r=T[x].r;
T[x].size=T[l].size+T[r].size+1-T[x].kill;
T[x].knum=T[l].knum+T[r].knum+T[x].kill;
for (int i=0;i<=1;i++){
if (l) T[x].mx[i]=max(T[x].mx[i],T[l].mx[i]),T[x].mn[i]=min(T[x].mn[i],T[l].mn[i]);
if (r) T[x].mx[i]=max(T[x].mx[i],T[r].mx[i]),T[x].mn[i]=min(T[x].mn[i],T[r].mn[i]);
}
}
inline void build(int &x,int l,int r,int k){
if (l>r) return;
int mid=l+r>>1;
D=k;
nth_element(h+l,h+mid,h+r+1,cmp);
x=h[mid];
T[x].size=1;
T[x].kill=0;
T[x].knum=0;
for (int i=0;i<=1;i++) T[x].mx[i]=T[x].mn[i]=T[x].d[i];
build(T[x].l,l,mid-1,k^1);
build(T[x].r,mid+1,r,k^1);
update(x);
}
inline void erase(int &x){
if (!x) return;
if (!T[x].kill) h[++tot]=x;
erase(T[x].l),erase(T[x].r);
x=0;
}
inline void rebuild(int &x,int k){
tot=0;
erase(x);
build(x,1,tot,k);
}
inline void insert(int &x,int k){
if (!x){
x=++cnt;
T[x].size=1;
T[x].kill=0;
T[x].knum=0;
for (int i=0;i<=1;i++) T[x].d[i]=T[x].mn[i]=T[x].mx[i]=q[i];
return;
}
if (q[k]<T[x].d[k]) insert(T[x].l,k^1);
else insert(T[x].r,k^1);
update(x);
if (max(T[T[x].l].size,T[T[x].r].size)>T[x].size*alpha||T[x].knum>T[x].size*alpha) rebuild(x,k);//如果你想当全站第五的话把这句去掉就行了
}
inline void del(int now,int x){
if (now==x){
T[x].kill=1;
for (int i=0;i<=1;i++) T[x].mx[i]=-1e9,T[x].mn[i]=1e9;
update(x);
return;
}
int l=T[now].l;
if (l&&T[l].mn[0]<=q[0]&&q[0]<=T[l].mx[0]&&T[l].mn[1]<=q[1]&&q[1]<=T[l].mx[1]) del(l,x);
else del(T[now].r,x);
update(now);
}
LL calc(int x){
if (!x) return -1e9;
return 1ll*T[x].mx[0]*q[0]+1ll*T[x].mx[1]*q[1];
}
inline void query(int now){
if (!T[now].kill) ans=max(ans,1ll*T[now].d[0]*q[0]+1ll*T[now].d[1]*q[1]);
LL al=calc(T[now].l),ar=calc(T[now].r);
if (al>ar){
if (al>ans) query(T[now].l);
if (ar>ans) query(T[now].r);
}
else{
if (ar>ans) query(T[now].r);
if (al>ans) query(T[now].l);
}
}
int main(){
read(n);
for (int i=1;i<=n;i++){
read(op);
if (op==1){
read(q[0]),read(q[1]);
insert(root,0);
ax[cnt]=q[0],ay[cnt]=q[1];
}
else if (op==2){
read(x);
q[0]=ax[x],q[1]=ay[x];
del(root,x);
}
else{
read(q[0]),read(q[1]);
ans=0;
query(root);
printf("%lld\n",ans);
}
}
return 0;
}