Description
传送门
n次操作。每次要么插入一个向量，要么查询对于按照插入顺序的区间的向量，求与向量(x,y)点积的最大值，即求最大的
x
1
x
2
+
y
1
y
2
x_1x_2+y_1y_2
x1x2+y1y2强制在线，n<=3e5，所有向量的x，y大于0
Solution
想了好久的几何做法，无果，直接无脑代数。然后就变成斜率优化了。区间询问就建一个线段树。每一个树上节点维护一个凸包。刚开始我以为这个带加点的凸包要用平衡树维护。实际上由于只有加点，所以只有当一个线段树节点满的时候才建凸包。这样子就是
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)的了。这题实际上是一道大模板套路题，但是我对于斜率优化的式子并不是十分理解，所以考场上我还手推了一波斜率优化：
斜率优化
最常见的斜率优化是对于每一个决策点的选择的贡献y，可以表示成一条直线，y=kx+b，根据x的变化，y就有一个最优的。根据这个求最小或最大维护一个上凸壳或下凸壳就好了。但是这题的贡献与两个东西有关，就不好清晰地理解这个优化。我们在学习斜率优化的时候经常会看到这样一个式子（或者稍微变一下符号）：
w
>
y
1
−
y
2
x
1
−
x
2
>
y
2
−
y
3
x
2
−
x
3
>
.
.
.
>
y
i
−
y
i
+
1
x
i
−
x
i
+
1
w>\frac{y1-y2}{x1-x2}>\frac{y2-y3}{x2-x3}>...>\frac{y_i-y_{i+1}}{x_i-x_{i+1}}
w>x1−x2y1−y2>x2−x3y2−y3>...>xi−xi+1yi−yi+1对于这个东西要维护一个单调队列。对于上面所说到的直线的理解方法自然可以将它理解为凸壳。同样对于这题来说，我们也假设每一个向量为(ai,bi)，考虑询问(x,y)对于两个向量i，j，如果ai<aj，并且i优于j，那么可以推出这个式子：
x
y
<
b
j
−
b
i
a
i
−
a
j
\frac{x}{y}<\frac{b_j-bi}{a_i-a_j}
yx<ai−ajbj−bi根据套路，就有：
x
y
<
b
j
−
b
i
a
i
−
a
j
<
b
k
−
b
j
a
j
−
a
k
.
.
.
.
\frac{x}{y}<\frac{b_j-b_i}{a_i-a_j}<\frac{b_k-b_j}{a_j-a_k}....
yx<ai−ajbj−bi<aj−akbk−bj....其中i最优。但是为什么有
b
j
−
b
i
a
i
−
a
j
<
b
k
−
b
j
a
j
−
a
k
\frac{b_j-b_i}{a_i-a_j}<\frac{b_k-b_j}{a_j-a_k}
ai−ajbj−bi<aj−akbk−bj呢？假定有：
x
y
<
b
j
−
b
i
a
i
−
a
j
,
x
y
<
b
k
−
b
j
a
j
−
a
k
,
b
j
−
b
i
a
i
−
a
j
>
b
k
−
b
j
a
j
−
a
k
\frac{x}{y}<\frac{b_j-bi}{a_i-a_j},\frac{x}{y}<\frac{b_k-b_j}{a_j-a_k},\frac{b_j-bi}{a_i-a_j}>\frac{b_k-b_j}{a_j-a_k}
yx<ai−ajbj−bi,yx<aj−akbk−bj,ai−ajbj−bi>aj−akbk−bj那么当j优于k的时候，因为
b
j
−
b
i
a
i
−
a
j
>
b
k
−
b
j
a
j
−
a
k
>
x
y
\frac{b_j-bi}{a_i-a_j}>\frac{b_k-b_j}{a_j-a_k}>\frac{x}{y}
ai−ajbj−bi>aj−akbk−bj>yx所以i也优于j，所以j就没有用了。所以才需要维护上面的一段递增的斜率。知道了这个之后以后就可以大力推式子，大胆用结论了，不用管是否能够表示在图像上了。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 300005
#define maxt 1000005
#define db double
using namespace std
;
int Q
,m
,cnt
,que
[maxn
][5],i
,j
,k
,ans
,L
,R
;
struct node
{
int x
,y
;
node(int _x
=0,int _y
=0){x
=_x
,y
=_y
;}
} P
,p
[maxn
],a
[maxn
],dd
[maxn
],d
[maxn
*20];
int operator
<(node a
,node b
){return a
.x
<b
.x
||a
.x
==b
.x
&&a
.y
>b
.y
;}
db
K(node a
,node b
){return 1.0*(b
.y
-a
.y
)/(a
.x
-b
.x
);}
void read(int &x
){
x
=0; char ch
=getchar();
for(;ch
<'0'||ch
>'9';ch
=getchar());
for(;ch
>='0'&&ch
<='9';ch
=getchar()) x
=x
*10+ch
-'0';
}
int st
[maxt
],en
[maxt
],tot
,n
,w
;
void Doit(int x
,int l
,int r
){
n
=w
=0;
for(int i
=l
;i
<=r
;i
++) a
[++n
]=p
[i
];
sort(a
+1,a
+1+n
);
for(int i
=1;i
<=n
;i
++) if (i
==1||a
[i
].x
!=a
[i
-1].x
){
while (w
>1&&K(dd
[w
],dd
[w
-1])>=K(a
[i
],dd
[w
])) w
--;
while (w
&&a
[i
].y
>=dd
[w
].y
) w
--;
dd
[++w
]=a
[i
];
}
st
[x
]=tot
+1,en
[x
]=tot
+w
;
for(int i
=1;i
<=w
;i
++) d
[tot
+i
]=dd
[i
];
tot
+=w
;
}
void insert(int x
,int l
,int r
,int y
){
if (y
==r
) Doit(x
,l
,r
);
if (l
==r
) return;
int mid
=(l
+r
)>>1;
if (y
<=mid
) insert(x
<<1,l
,mid
,y
);
else insert((x
<<1)^1,mid
+1,r
,y
);
}
int Mul(node a
,node b
){return a
.x
*b
.x
+a
.y
*b
.y
;}
void Get(int x
){
int l
=st
[x
],r
=en
[x
]-1;
ans
=max(ans
,Mul(d
[en
[x
]],P
));
while (l
<=r
){
int mid
=(l
+r
)/2;
ans
=max(ans
,Mul(d
[mid
],P
));
if (K(d
[mid
],d
[mid
+1])<=1.0*P
.x
/P
.y
) l
=mid
+1;
else r
=mid
-1;
}
}
void find(int x
,int l
,int r
){
if (l
>R
||r
<L
) return;
if (L
<=l
&&r
<=R
) {Get(x
);return;}
int mid
=(l
+r
)>>1;
find(x
<<1,l
,mid
),find((x
<<1)^1,mid
+1,r
);
}
int main(){
read(Q
);
for(i
=1;i
<=Q
;i
++){
read(que
[i
][0]);
if (que
[i
][0]==1) read(que
[i
][1]),read(que
[i
][2]),m
++;
else read(que
[i
][1]),read(que
[i
][2]),read(que
[i
][3]),read(que
[i
][4]);
}
for(int q
=1;q
<=Q
;q
++){
int opt
=que
[q
][0];
if (opt
==1){
p
[++cnt
]=node(que
[q
][1]^ans
,que
[q
][2]^ans
);
insert(1,1,m
,cnt
);
} else {
L
=que
[q
][3]^ans
,R
=que
[q
][4]^ans
;
P
=node(que
[q
][1]^ans
,que
[q
][2]^ans
);
ans
=0,find(1,1,m
);
printf("%d\n",ans
);
}
}
}
