题解：
码力太差重构之后才$A……$
首先求向量点积最大很容易想到凸包，
设已知$(x_0,y_0)$，求$(x,y)$满足$(x,y)*(x_0,y_0)>=(x',y')*(x_0,y_0)$
设$(x,y)*(x_0,y_0)=c$
那么$x*x_0+y*y_0=c$，$y=frac(-x_0,y_0)*x+frac(c,x_0)$
所以$x_0>0$时，$b$取最大，维护上凸包；
$x_0<0$时，$b$取最小，维护下凸包。
其实$x_0=0$不需要单独维护，放到任意一堆里二分都行。
由于询问与时间序有关，我们可以按时间建线段树，
每个节点挂一个凸包。
每次询问时从对应凸包二分查最大点积。
插入时并不需要每插一个点就把这个凸包拆开重构，
只需要在子树插满，即$r=x$时建立凸包即可。
代码：
#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; const int N = 400050; typedef long long ll; const ll inf = 0x3f3f3f3f3f3f3f3fll; const double eps = 1e16; int n,tot; ll ans; char s0[5],s[5]; struct Point { ll x,y; Point(){} Point(ll x,ll y):x(x),y(y){} ll operator * (const Point&a)const{return x*a.x+y*a.y;} ll operator ^ (const Point&a)const{return y*a.x-x*a.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);} bool operator < (const Point&a)const{return x==a.x?y<a.y:x<a.x;} }; vector<Point>tmp[N<<2],c1[N<<2],c2[N<<2]; struct segtree { void insert(int l,int r,int u,ll x,ll y,int z) { tmp[u].push_back(Point(x,y)); if(z==r) { sort(tmp[u].begin(),tmp[u].end()); for(int i=0;i<tmp[u].size();i++) { while(c1[u].size()>1&&((c1[u][c1[u].size()-1]-c1[u][c1[u].size()-2])^(tmp[u][i]-c1[u][c1[u].size()-1]))<=0)c1[u].pop_back(); c1[u].push_back(tmp[u][i]); while(c2[u].size()>1&&((c2[u][c2[u].size()-1]-c2[u][c2[u].size()-2])^(tmp[u][i]-c2[u][c2[u].size()-1]))>=0)c2[u].pop_back(); c2[u].push_back(tmp[u][i]); } } if(l==r)return ; int mid = (l+r)>>1; if(z<=mid)insert(l,mid,u<<1,x,y,z); else insert(mid+1,r,u<<1|1,x,y,z); } void query(int l,int r,int u,Point p,int ql,int qr) { if(l==ql&&r==qr) { if(p.y>=0) { int L = 1,R = c1[u].size()-1,as = 0; while(L<=R) { int mid = (L+R)>>1; if(p*c1[u][mid]>p*c1[u][mid-1])as=mid,L=mid+1; else R=mid-1; } ans=max(ans,p*c1[u][as]); }else { int L = 1,R = c2[u].size()-1,as = 0; while(L<=R) { int mid = (L+R)>>1; if(p*c2[u][mid]>p*c2[u][mid-1])as=mid,L=mid+1; else R=mid-1; } ans=max(ans,p*c2[u][as]); } return ; } int mid = (l+r)>>1; if(qr<=mid)query(l,mid,u<<1,p,ql,qr); else if(ql>mid)query(mid+1,r,u<<1|1,p,ql,qr); else query(l,mid,u<<1,p,ql,mid),query(mid+1,r,u<<1|1,p,mid+1,qr); } }tr; int main() { scanf("%d%s",&n,s0); for(int x,y,l,r,i=1;i<=n;i++) { scanf("%s%d%d",s,&x,&y); if(s0[0]!='E')x^=ans,y^=ans; if(s[0]=='A') { tot++; tr.insert(1,n,1,x,y,tot); }else { scanf("%d%d",&l,&r); if(s0[0]!='E')l^=ans,r^=ans; ans=-inf; tr.query(1,n,1,Point(x,y),l,r); printf("%lld ",ans); ans&=0x7fffffff; } } return 0; }