题目
题目描述
维护一个向量集合，在线支持以下操作：
- “A x y $(\vert x\vert ，\vert y\vert \le 10^8)$”：加入向量(x，y);
- ” Q x y l r $(\vert x\vert，\vert y\vert \le 10^8，1 \le L \le R \le T)$，其中T为已经加入的向量个数)询问第L个到第R个加入的向量与向量(x，y)的点积的最大值。
集合初始时为空。
输入输出格式
输入格式：
输入的第一行包含整数N和字符s，分别表示操作数和数据类别； 接下来N行，每行一个操作，格式如上所述。
请注意s≠’E’时，输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入：
inline int decode (int x long long lastans) {
return x ^ (lastans & 0x7fffffff); }
其中x为程序读入的数，lastans为之前最后一次询问的答案。在第一次询问之前，lastans=0。注：向量(x，y)和(z，W)的点积定义为xz+yw。
输出格式：
对每个Q操作，输出一个整数表示答案。
输入输出样例
输入样例#1：
6 A
A 3 2
Q 1 5 1 1
A 15 14
A 12 9
Q 12 8 12 15
Q 21 18 19 18
输出样例#1：
13
17
17
说明
1 < =N < =4*10^5
题解
看到向量，就想到构建凸包（大雾
因为要求点积的最大值，设点积为$t$，则有$t=xx’+yy’$（$(x,y)$为询问向量）
移一下项，同除$y$，$y’=\frac{-xx’+t}{y}$
这就是一个关于$x’,y’$的一次函数，要求的是$t$的最大值，所以分$y$的正负性讨论一下在上凸壳还是在下凸壳求，在上下凸壳上三分一下就行
然后y你分正负讨论一下发现还是可以直接比较点积
癌怎么维护凸包啊……
这太简单了写个线段树套平衡树维护动态凸包就行了
因为查询的区间肯定都是满区间，所以等一个区间满了的时候一次性构造凸包就行了
时间复杂度是$O(n\log^2n)$的
因为凸包的比较函数写错了调了一下午+一晚上……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<cmath>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=4e5+5;
struct Point{
int x,y;
Point(int X=0,int Y=0) {x=X,y=Y;}
bool operator< (const Point &a)
const{
if(x!=a.x) return x<a.x;
return y<a.y;
}
}_P[MAX],H;
struct p{
int l,r,Top,cnt,str,_L;
}s[MAX<<2];
int n,rt,tot,cnt,_cnt,__cnt;
LL ans;
int st[MAX<<4];
bool FL;
vector<Point> __P[MAX<<3];
int read(LL ans=0)
{
int x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
x=x*fl;
if(FL) x=x^(ans&0x7fffffff);
return x;
}
Point operator- (Point x,Point y) {return Point(x.x-y.x,x.y-y.y);}
LL Cross(Point x,Point y) {return 1ll*x.x*y.y-1ll*x.y*y.x;}
LL Dot(Point x,Point y) {return 1ll*x.x*y.x+1ll*x.y*y.y;}
LL Cmp(Point a,Point b,Point c) {return Cross(b-a,c-a);}
bool cmp(Point a,Point b)
{
if(!Cmp(H,a,b)) return a<b;
return Cmp(H,a,b)>0;
}
char Read()
{
char ch=getchar();
for(;!isalpha(ch);ch=getchar());
return ch;
}
void GET_HULL(int k)
{
if(s[k].cnt==1) return;
sort(__P[k].begin(),__P[k].end()),H=__P[k][0],st[s[k].Top=++_cnt]=0,sort(__P[k].begin()+1,__P[k].end(),cmp),s[k].str=_cnt;
for(int i=1;i<s[k].cnt;++i)
{
while(s[k].Top>_cnt&&Cross(__P[k][st[s[k].Top]]-__P[k][st[s[k].Top-1]],__P[k][i]-__P[k][st[s[k].Top]])<=0) --s[k].Top;
st[++s[k].Top]=i;
}
_cnt=s[k].Top,s[k]._L=s[k].Top;
for(int i=s[k].str;i<s[k].Top;++i)
if(__P[k][st[i]].x>=__P[k][st[i+1]].x) {s[k]._L=i;break;}
++_cnt,st[++s[k].Top]=0;
}
LL GET_B(Point A,Point B) {return Dot(A,B);}
LL GET_UP(int k,Point A)
{
if(s[k].cnt==1) return Dot(__P[k][0],A);
int l=s[k]._L,r=s[k].Top;
while(l+3<=r)
{
int midl=(l+r>>1),midr=(midl+r>>1);
if(GET_B(A,__P[k][st[midl]])>GET_B(A,__P[k][st[midr]])) r=midr;
else l=midl;
}
LL Ans=-1e18;
for(int i=l;i<=r;++i)
Ans=max(Ans,Dot(__P[k][st[i]],A));
return Ans;
}
LL GET_DOWN(int k,Point A)
{
if(s[k].cnt==1) return Dot(__P[k][0],A);
int l=s[k].str,r=s[k]._L;
while(l+3<=r)
{
int midl=l+r>>1,midr=midl+r>>1;
if(GET_B(A,__P[k][st[midl]])>GET_B(A,__P[k][st[midr]])) r=midr;
else l=midl;
}
LL Ans=-1e18;
for(int i=l;i<=r;++i)
Ans=max(Ans,Dot(__P[k][st[i]],A));
return Ans;
}
LL ask(int l,int r,int k,int L,int R,Point A)
{
if(r<L||R<l) return -1e18;
if(l>=L&&r<=R) return max(GET_UP(k,A),GET_DOWN(k,A));
if(R<=mid) return ask(l,mid,tl,L,R,A);
if(L>mid) return ask(mid+1,r,tr,L,R,A);
return max(ask(l,mid,tl,L,R,A),ask(mid+1,r,tr,L,R,A));
}
void change(int l,int r,int &k,int x)
{
if(!k) k=++tot;
__P[k].push_back(_P[x]),++s[k].cnt;
if(s[k].cnt==r-l+1) GET_HULL(k);
if(l==r) return;
if(x<=mid) change(l,mid,tl,x);
else change(mid+1,r,tr,x);
}
int main()
{
n=read(),FL=(Read()=='E'?0:1);
for(int i=1,x,y,l,r,L=0;i<=n;++i)
{
char A=Read();
x=read(ans),y=read(ans);
if(A=='Q') l=read(ans),r=read(ans),printf("%lld\n",ans=ask(1,n,rt,l,r,Point(x,y)));
else if(A=='A') _P[++L]=Point(x,y),change(1,n,rt,L);
}
return 0;
}
