[SDOI2014]向量集
题目描述
维护一个向量集合，在线支持以下操作： - "A x y (|x|，|y| < =10^8)"：加入向量(x，y); - " Q x y l r (|x|，|y| < =10^8，1 < =L < =R < =T，其中T为已经加入的向量个数)询问第L个到第R个加入的向量与向量(x，y)的点积的最大值。 集合初始时为空。
输入输出格式
输入格式
输入的第一行包含整数N和字符s，分别表示操作数和数据类别； 接下来N行，每行一个操作，格式如上所述。 请注意s≠'E'时，输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入： ··· inline int decode (int x long long lastans) { return x ^ (lastans & Ox7fffffff); } ``` 其中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
说明
样例解释：解密之后的输入为 ``` 6 E A 3 2 Q 1 5 1 1 A 2 3 A 1 4 Q 1 5 1 2 Q 4 3 2 3 ``` 1 < =N < =4*10^5
[题意]
维护向量序列，支持在序列末尾添加向量，以及询问某个区间中的向量与给定向量的点积的最大值。
[官方题解]
[个人题解]（网上东拼西凑的）
一般性设当前询问的$y_0>0$，那么$dfrac{ans}{y_0}=max{dfrac{x_0}{y_0}cdot x+y}$，然后这个东西和斜率优化长得一样，答案一定是在凸壳上的.
于是我们维护这个凸壳.因为有区间询问所以线段树维护每个区间的凸壳.具体地，插入的时候统计当前区间已经有多少个点，如果点数等于当前区间长度那么构造出这个区间的凸壳.询问的时候拆成$log$个区间分别跑二分/三分即可.
求凸包这里使用按$x$坐标排序的那个算法.注意如果几个点的$x$相同那么要按$y$排序.
插入的时候每个区间只会被构建一次凸包，总复杂度$O(nlog n)$，排序用归并.
查询的时候拆成$log$个区间，每个区间$O(log n)$三分/二分，总复杂度$O(nlog ^2 n)$
每个区间都要构建一次凸包，可以这么处理：每个线段树节点放个指针，动态开辟空间建立凸包。
网上不少代码把情况讨论合并成一种，只维护上凸壳。保险起见，也为了自己能够更好地理解，我还是分类讨论，同时维护上下凸壳。
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; inline void read(int &x){ register char ch=getchar();x=0;register bool f=0; for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1; for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; if(f) x=-x; } const int N=4e5+3; int n,m,cnt;ll ans;char type[3],op[3]; struct Q{ int opt,l,r,x,y; Q(){} Q(int opt,int l,int r,int x,int y):opt(opt),l(l),r(r),x(x),y(y){} }q[N]; struct point{ int x,y; point(int x=0,int y=0):x(x),y(y){} point operator +(const point &a)const{ return point(x+a.x,y+a.y); } point operator -(const point &a)const{ return point(x-a.x,y-a.y); } ll operator *(const point &a)const{ return (ll)x*a.x+(ll)y*a.y; } ll operator ^(const point &a){ return (ll)x*a.y-(ll)y*a.x; } bool operator <(const point &a)const{ return x==a.x?y<a.y:x<a.x; } }p[N],tmp[N];int tmpsize; struct CH{ point *up,*dw; int upsize,dwsize; void init(int l,int r){ up=new point[r-l+2]; dw=new point[r-l+2]; tmpsize=upsize=dwsize=0; for(int i=l;i<=r;i++) tmp[++tmpsize]=p[i]; sort(tmp+1,tmp+tmpsize+1); for(int i=1;i<=tmpsize;i++){ for(;upsize>1&&((tmp[i]-up[upsize])^(up[upsize]-up[upsize-1]))<=0;upsize--); up[++upsize]=tmp[i]; for(;dwsize>1&&((dw[dwsize]-dw[dwsize-1])^(tmp[i]-dw[dwsize]))<=0;dwsize--); dw[++dwsize]=tmp[i]; } } ll qmax(point p){ int l,r,mid1,mid2;ll res=-(1LL<<62); if(p.y>=0){ l=1;r=upsize; while(r-l>2){ mid1=l+(r-l)/3; mid2=r-(r-l)/3; if(up[mid1]*p<up[mid2]*p) l=mid1; else r=mid2; } for(int i=l;i<=r;i++) res=max(res,up[i]*p); } else{ l=1;r=dwsize; while(r-l>2){ mid1=l+(r-l)/3; mid2=r-(r-l)/3; if(dw[mid1]*p<dw[mid2]*p) l=mid1; else r=mid2; } for(int i=l;i<=r;i++) res=max(res,dw[i]*p); } return res; } }b[N<<2];bool tag[N<<2]; #define lch k<<1 #define rch k<<1|1 ll query(int k,int l,int r,int x,int y,point p){ if(l==x&&r==y){ if(!tag[k]) tag[k]=1,b[k].init(l,r); return b[k].qmax(p); } int mid=l+r>>1; if(y<=mid) return query(lch,l,mid,x,y,p); else if(x>mid) return query(rch,mid+1,r,x,y,p); else return max(query(lch,l,mid,x,mid,p),query(rch,mid+1,r,mid+1,y,p)); } inline void decode(int &x){ if(type[0]=='E') return ; x=x^(ans&0x7fffffff); } int main(){ read(m);scanf("%s",type); for(int i=1,opt,x,y,l,r;i<=m;i++){ scanf("%s",op);opt=(op[0]=='Q'); if(opt){ read(x);read(y); read(l);read(r); } else{ read(x);read(y);l=r=0; ++n; } q[i]=Q(opt,l,r,x,y); } for(int i=1,l,r,x,y;i<=m;i++){ if(q[i].opt){ l=q[i].l;r=q[i].r; x=q[i].x;y=q[i].y; decode(l);decode(r); decode(x);decode(y); ans=query(1,1,n,l,r,point(x,y)); printf("%lld ",ans); } else{ x=q[i].x;y=q[i].y; decode(x);decode(y); p[++cnt]=point(x,y); } } return 0; }
收获：
所有形如$f[i]=minlimits_{L(i)leq jleq R(i)}{k(i)x(j)+F(j)}+G(i)$的$dp$都是可做的（斜率优化型动态规划）