Fork me on GitHub

Uoj#40.【清华集训2014】卡常数

Uoj#40. 【清华集训2014】卡常数

题意:

  • 三维空间中有$n$个点。
  • 每次询问距离给出点为某个距离的点是什么或者修改一个点的坐标。
  • 操作参数加密,所有坐标随机生成。
  • $n,m\le 65536$。

题解:

  • 首先加密函数考虑$f(x)=ax-b\sin(x)$。
  • $f’(x)=a-b\cos(x)$。
  • 而$a>b\ge0$,所以$f(x)$单调递增。
  • 所以我们可以二分来解密。
  • 听说标算是个很厉害的利用加密特点的做法。
  • 但我并没有看懂。。
  • 但是这题还是可以直接上$\rm KD-Tree$。
  • 因为坐标是随机生成,所以什么根据方差来选择哪一维就不必要了,直接按顺序选择三维就可以了。
  • 查询大概就是:
    • 维护出每个子空间中所有点的$x,y,z$的最大最小值。
    • 设置最近函数为:
      • 对于每一维,如果坐标在最大最小之间,设为$0$。
      • 否则设置为与其中较近的距离。
    • 设置最远函数为:
      • 每一维距离取与最大最小值差的较大值。
    • 然后对于每个其中可能存在答案的子空间递归查找。
  • 修改大概就是直接暴力插入点,删除原先点并维护其相关信息。
  • 因为数据随机,所以不需要替罪羊树暴力重构的方法。
  • 复杂度$O((n+m)\sqrt{n})$。

代码:

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#include <bits/stdc++.h>
#define nxt(x) ((x+1)%3)
#define sqr(x) ((x)*(x))
using namespace std;
const int N=1<<18;
const double inf=1e3;
const double eps=1e-5;
int mode;
struct point
{
double x,y,z;
point(double x=0,double y=0,double z=0):x(x),y(y),z(z){}
};
point getmin(const point &A,const point &B)
{
return point(min(A.x,B.x),min(A.y,B.y),min(A.z,B.z));
}
point getmax(const point &A,const point &B)
{
return point(max(A.x,B.x),max(A.y,B.y),max(A.z,B.z));
}
double dis(const point &A,const point &B)
{
return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y)+sqr(A.z-B.z));
}
bool operator <(const point &A,const point &B)
{
if (mode==0) return A.x<B.x;
else if (mode==1) return A.y<B.y;
else return A.z<B.z;
}
bool operator >(const point &A,const point &B)
{
if (mode==0) return A.x>B.x;
else if (mode==1) return A.y>B.y;
else return A.z>B.z;
}
struct node
{
point p;
bool vis;
int id;
bool operator <(const node &rhs) const
{
return p<rhs.p;
}
bool operator >(const node &rhs) const
{
return p>rhs.p;
}
};
int n,m;
double AA,BB;
struct KDT
{
struct Node
{
node val;
int ls,rs,mode,fa;
point Min,Max;
}a[N];
node b[N];
int root,cnt,pos[N];
void up(int now)
{
if (a[now].val.vis) a[now].Min=a[now].Max=a[now].val.p;
else
{
a[now].Min=point(inf,inf,inf);
a[now].Max=point(-inf,-inf,-inf);
}
if (a[now].ls)
{
a[now].Min=getmin(a[now].Min,a[a[now].ls].Min);
a[now].Max=getmax(a[now].Max,a[a[now].ls].Max);
}
if (a[now].rs)
{
a[now].Min=getmin(a[now].Min,a[a[now].rs].Min);
a[now].Max=getmax(a[now].Max,a[a[now].rs].Max);
}
}
void build(int &cur,int l,int r,int Mode)
{
a[cur=++cnt].mode=mode=Mode;
int mid=(l+r)>>1;
nth_element(b+l,b+mid,b+r+1);
a[cur].val=b[mid];
pos[a[cur].val.id]=cur;
if (l<mid)
{
build(a[cur].ls,l,mid-1,nxt(Mode));
a[a[cur].ls].fa=cur;
}
if (mid<r)
{
build(a[cur].rs,mid+1,r,nxt(Mode));
a[a[cur].rs].fa=cur;
}
up(cur);
}
void init(int n)
{
root=cnt=0;
memset(pos,0,sizeof(pos));
for (int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&b[i].p.x,&b[i].p.y,&b[i].p.z);
b[i].vis=1,b[i].id=i;
}
build(root,1,n,0);
}
void push_up(int cur)
{
up(cur);
if (cur==root) return;
push_up(a[cur].fa);
}
void ins(int &cur,int Mode,node val)
{
if (!cur)
{
a[cur=++cnt].val=val;
a[cur].mode=Mode;
pos[a[cur].val.id]=cur;
up(cur);
return;
}
mode=Mode;
if (val<a[cur].val)
{
ins(a[cur].ls,nxt(Mode),val);
a[a[cur].ls].fa=cur;
}
else
{
ins(a[cur].rs,nxt(Mode),val);
a[a[cur].rs].fa=cur;
}
up(cur);
}
void modify(int x,point p)
{
a[pos[x]].val.vis=0;
push_up(pos[x]);
ins(root,0,(node){p,true,x});
}
double nearest(int cur,point p)
{
double x,y,z;
if (a[cur].Min.x>p.x) x=a[cur].Min.x-p.x;
else if (a[cur].Max.x<p.x) x=p.x-a[cur].Max.x;
else x=0;
if (a[cur].Min.y>p.y) y=a[cur].Min.y-p.y;
else if (a[cur].Max.y<p.y) y=p.y-a[cur].Max.y;
else y=0;
if (a[cur].Min.z>p.z) z=a[cur].Min.z-p.z;
else if (a[cur].Max.z<p.z) z=p.z-a[cur].Max.z;
else z=0;
return sqrt(sqr(x)+sqr(y)+sqr(z));
}
double farthest(int cur,point p)
{
double x=max(fabs(a[cur].Min.x-p.x),fabs(a[cur].Max.x-p.x));
double y=max(fabs(a[cur].Min.y-p.y),fabs(a[cur].Max.y-p.y));
double z=max(fabs(a[cur].Min.z-p.z),fabs(a[cur].Max.z-p.z));
return sqrt(sqr(x)+sqr(y)+sqr(z));
}
int qry(int cur,point p,double d)
{
if (!cur) return 0;
if (nearest(cur,p)>d+eps||farthest(cur,p)<d-eps) return 0;
if (a[cur].val.vis&&fabs(d-dis(a[cur].val.p,p))<eps)
return a[cur].val.id;
int ret=0;
ret=qry(a[cur].ls,p,d);
if (ret) return ret;
ret=qry(a[cur].rs,p,d);
return ret;
}
}kdt;
double last_res=0.1;
double f(double x)
{
return AA*x-BB*sin(x);
}
double get(double l,double r,double val)
{
while (r-l>=1e-9)
{
double mid=(l+r)/2;
if (f(mid*last_res+1)>val) r=mid;
else l=mid;
}
return (l+r)/2;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
scanf("%lf%lf",&AA,&BB);
kdt.init(n);
while (m--)
{
int op;
scanf("%d",&op);
if (op==0)
{
double t,x,y,z;
scanf("%lf%lf%lf%lf",&t,&x,&y,&z);
int id=get(1,n,t)+0.5;
x=get(-inf,inf,x);
y=get(-inf,inf,y);
z=get(-inf,inf,z);
kdt.modify(id,point(x,y,z));
}
else
{
double x,y,z,t;
scanf("%lf%lf%lf%lf",&x,&y,&z,&t);
x=get(-inf,inf,x);
y=get(-inf,inf,y);
z=get(-inf,inf,z);
t=get(-inf,inf,t);
int ret=kdt.qry(kdt.root,point(x,y,z),t);
printf("%d\n",ret);
last_res=ret;
}
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#40.【清华集训2014】卡常数

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj40/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。