bzoj3533题解

容易发现答案一定在凸包上,询问的$y\lt 0$则在上凸壳,否则在下凸壳.

容易发现$A\cup B$凸包上的点一定在$A$或$B$的凸包上,所以可以考虑用线段树来维护,每个节点保存对应区间的凸包,每个询问查询$\mathcal O(\log n)$个线段树上的节点.

但是这里有一个问题,凸包无法高效合并,插入也很麻烦,但是如果知道最后的点集的话离线构建是非常容易的. 这种情况一般可以考虑二进制分组. 对于本题,把二进制分组放到线段树上,也就是说当一个节点对应的区间被填满的时候,再构建这个节点的凸包.

有一个细节一定要记住:求凸壳的时候两维坐标都要排序:从大到小和从小到大都没问题,两个维度顺序相反也没问题,但是一定要排序. 我也不是很清楚为什么. 以后遇到给struct排序的情况,最好是给每一个属性都定一个顺序.

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ele long long
using namespace std;
#define maxn 400010
const ele M=1<<19;
const ele size=M<<1;
struct pt{
ele x,y;
inline bool operator<(pt b)const{
return x!=b.x?x<b.x:y<b.y;
}
}p[maxn];
inline pt operator+(pt a,pt b){
return (pt){a.x+b.x,a.y+b.y};
}
inline pt operator-(pt a,pt b){
return (pt){a.x-b.x,a.y-b.y};
}
inline ele dot(pt a,pt b){
return a.x*b.x+a.y*b.y;
}
inline ele cross(pt a,pt b){
return a.x*b.y-a.y*b.x;
}
ele n,lastans,a[size];
char ty[10];
vector<pt> v1[size],v2[size];
inline ele decode(ele x){
return x^(lastans&0x7fffffff);
}
inline void maintain(ele i){
a[i]=a[i<<1]+a[i<<1|1];
}
inline void build(vector<pt>&v1,vector<pt>&v2,ele l,ele r){
ele top=0;
static pt q[maxn];
memcpy(q,p+l,sizeof(pt)*(r-l+1));
sort(q,q+r-l+1);
for (int i=l; i<=r; ++i){
while (top>1 && cross(v1[top-1]-v1[top-2],q[i-l]-v1[top-1])>=0) --top,v1.pop_back();
v1.push_back(q[i-l]);
++top;
}
top=0;
for (int i=l; i<=r; ++i){
while (top>1 && cross(v2[top-1]-v2[top-2],q[i-l]-v2[top-1])<=0) --top,v2.pop_back();
v2.push_back(q[i-l]);
++top;
}
}
inline void upd(ele i){
ele L=1,j=i; i+=M;
for (; i; i>>=1,L<<=1){
++a[i];
if (a[i]==L) build(v1[i],v2[i],j-L+1,j);
}
}
inline ele qry(vector<pt>&v,pt p){
ele L=-1,R=v.size()-1;
while (R-L>1){
ele mid=(L+R)>>1;
if (dot(v[mid],p)<=dot(v[mid+1],p)) L=mid; else R=mid;
}
return dot(v[R],p);
}
inline ele qry(ele l,ele r,pt p){
ele ans=-1e18;
for (l=l+M-1,r=r+M+1; l^r^1; l>>=1,r>>=1){
if (~l&1) ans=max(ans,p.y>0?qry(v1[l^1],p):qry(v2[l^1],p));
if (r&1) ans=max(ans,p.y>0?qry(v1[r^1],p):qry(v2[r^1],p));
}
return ans;
}
int main(){
scanf("%lld%s",&n,ty);
memset(a,0,sizeof(a));
lastans=0;
ele i=1;
while (n--){
char op[5];
ele x,y,l,r;
scanf("%s%lld%lld",op,&x,&y);
if (ty[0]!='E') x=decode(x),y=decode(y);
if (op[0]=='A'){
p[i]=(pt){x,y};
upd(i);
++i;
}
else{
scanf("%lld%lld",&l,&r);
if (ty[0]!='E') l=decode(l),r=decode(r);
printf("%lld\n",lastans=qry(l,r,(pt){x,y}));
}
}
return 0;
}