设(x,y)为Q的查询点，分类讨论如下：
1、y>0: 最大化a*x+b*y，维护一个上凸壳三分即可
2、y<0：最大化a*x+b*y 维护一个下凸壳三分即可
我们考虑对时间建出一棵线段树
对于每个区间，如果满了就做出两个凸壳
总时间复杂度是O(n*log^2n)
之后我们考虑查询，每个区间最多被分解为log(n)个区间
在每个区间的凸壳上三分最优解即可
至于优化，可以设定一个阈值，当区间长度小于阈值时不用做凸壳，查询时直接暴力就可以了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std; typedef long long LL;
const int maxn=400010;
const LL oo=1LL<<60;
char s,Q;
int n,cnt,a,b,T,TA,TB;
LL ans; struct Point{
int x,y;
Point(int x=0,int y=0):x(x),y(y){}
}p[maxn],tmp[maxn],now,A[4000010],B[4000010];
typedef Point Vector;
Vector operator -(const Point &A,const Point &B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator +(const Point &A,const Point &B){return Vector(A.x+B.x,A.y+B.y);}
inline LL Dot(const Point &A,const Point &B){return 1LL*A.x*B.x+1LL*A.y*B.y;}
inline LL Cross(const Point &A,const Point &B){return 1LL*A.x*B.y-1LL*A.y*B.x;} struct Seg_Tree{
int L,R;
int AL,AR;
int BL,BR;
}t[maxn<<2]; bool cmp1(const Point &a,const Point &b){
if(a.x==b.x)return a.y>b.y;
return a.x<b.x;
}
bool cmp2(const Point &a,const Point &b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
inline void decode(int &x){x=(s=='E'?x:x=x^(ans&0x7fffffff));}
inline void Get(char &ch){
ch=getchar();
while(ch<'!')ch=getchar();
}
inline void read(int &num){
num=0;int f=1;char ch;Get(ch);
if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
num*=f;
}
void build(int o,int L,int R){
t[o].L=L;t[o].R=R;
if(L==R)return;
int mid=(L+R)>>1;
build(o<<1,L,mid);
build(o<<1|1,mid+1,R);
}
void add(int o){
int L=t[o].L,R=t[o].R;
int mid=(L+R)>>1;
if(R==cnt&&R-L>=70){
T=0;
for(int i=L;i<=R;++i)tmp[++T]=p[i];
sort(tmp+1,tmp+T+1,cmp1);
A[++TA]=tmp[1];t[o].AL=TA;
for(int i=2;i<=T;++i){
if(tmp[i].x!=tmp[i-1].x){
while(TA>t[o].AL&&Cross(tmp[i]-A[TA],A[TA]-A[TA-1])<=0)TA--;
A[++TA]=tmp[i];
}
}t[o].AR=TA;
sort(tmp+1,tmp+T+1,cmp2);
B[++TB]=tmp[1];t[o].BL=TB;
for(int i=2;i<=T;++i){
if(tmp[i].x!=tmp[i-1].x){
while(TB>t[o].BL&&Cross(tmp[i]-B[TB],B[TB]-B[TB-1])>=0)TB--;
B[++TB]=tmp[i];
}
}t[o].BR=TB;
}
if(L==R)return;
if(cnt<=mid)add(o<<1);
else add(o<<1|1);
}
LL Get_A(int L,int R){
while(R-L>=3){
int m1=(L+L+R)/3,m2=(R+R+L)/3;
if(Dot(now,A[m1])>Dot(now,A[m2]))R=m2;
else L=m1;
}
LL ans=-oo;
for(int i=L;i<=R;++i)ans=max(ans,Dot(now,A[i]));
return ans;
}
LL Get_B(int L,int R){
while(R-L>=3){
int m1=(L+L+R)/3,m2=(R+R+L)/3;
if(Dot(now,B[m1])>Dot(now,B[m2]))R=m2;
else L=m1;
}
LL ans=-oo;
for(int i=L;i<=R;++i)ans=max(ans,Dot(now,B[i]));
return ans;
}
LL Get_ask(int o){
LL ans=-oo;
int L=t[o].L,R=t[o].R;
int mid=(L+R)>>1;
if(a<=L&&R<=b){
if(R-L<70)for(int i=L;i<=R;++i)ans=max(ans,Dot(now,p[i]));
else if(now.y>0)ans=Get_A(t[o].AL,t[o].AR);
else ans=Get_B(t[o].BL,t[o].BR);
return ans;
}
if(b<=mid)return Get_ask(o<<1);
else if(a>mid)return Get_ask(o<<1|1);
else return max(Get_ask(o<<1),Get_ask(o<<1|1));
} int main(){
read(n);Get(s);build(1,1,n);
for(int i=1;i<=n;++i){
Get(Q);
if(Q=='A'){
++cnt;
read(p[cnt].x);read(p[cnt].y);
decode(p[cnt].x);decode(p[cnt].y);
add(1);
}else{
read(now.x);read(now.y);
decode(now.x);decode(now.y);
read(a);read(b);
decode(a);decode(b);
ans=Get_ask(1);
printf("%lld\n",ans);
}
}return 0;
}