xz+yw=ans
w+x/y*z=ans/y
w=-x/y*z+ans/y
ans/y表示过点(z,w)的斜率为-x/y的直线在y轴上的截距
当y>0时，截距越大，ans越大，在上凸壳上找答案
当y<0时，截距越小，ans越大，在下凸壳上找答案
答案可以三分，也可以直接set维护斜率找斜率最接近的那个点
问题来了，如何维护区间[L,R]的凸包
线段树的每个节点建凸包是O(size log n)的
所以把所有的节点都建出凸包是O(∑size log n)的
因为O(∑size)=O(n log n)一层有n个点，有log n层
所以总复杂度是O(n log^2 n)的，空间复杂度是O(n log n)的
但是，题目要求在线插入，也就是说不能预处理出整棵线段树
如果暴力插入，每次要修改O(log n)个节点，每个节点复杂度为O(size)的，每次修改的复杂度是O(nlogn)。
如果每个节点用平衡树来维护的话是O(log size)的，复杂度就是O(log^2 n)的
我们发现，如果当前插入的节点为i，那么有一些节点是现在不会询问到的，那么就并不需要更新
每个节点打一个标记表示是否维护过，对于新插入节点的祖先，如果包含不会询问的节点，就不新建
因为每个节点只会被新建一次，所以复杂度是O(nlog^2n)的
或者，有更优的方法，我们何必建出那些不会被询问的节点呢？
所以，每次询问的时候再去新建就可以，复杂度也是O(nlog^2n)的
我还真是日了狗，第二次了，本机AC，bz上RE，求解释呀！！！
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#define maxn 500010
#define inf 1000000000000000000ll
using namespace std;
struct yts2
{
long long x,y;
}p[maxn];
long long operator*(yts2 a,yts2 b)
{
return a.x*b.y-a.y*b.x;
}
long long operator^(yts2 a,yts2 b)
{
return a.x*b.x+a.y*b.y;
}
yts2 operator-(yts2 x,yts2 y)
{
yts2 ans;
ans.x=x.x-y.x;ans.y=x.y-y.y;
return ans;
}
struct yts
{
int l,r;
bool flag;
int sizeup,sizedw;
vector<int> up,dw;
}t[4*maxn];
struct yts1
{
int op;
int x,y;
int l,r;
}q[maxn];
int decode(int x,long long ans)
{
return x^(ans&0x7fffffff);
}
bool cmp(int i,int j)
{
return p[i].x<p[j].x || (p[i].x==p[j].x && p[i].y<p[j].y);
}
int n,m,T,tot,tmp[maxn];
long long ans;
char s1[5],s[5];
void build(int i,int l,int r)
{
t[i].l=l;t[i].r=r;t[i].flag=0;
for (int j=l;j<=r+1;j++) t[i].up.push_back(0),t[i].dw.push_back(0);
if (l==r) return;
int mid=(l+r)/2;
build(i*2,l,mid);build(i*2+1,mid+1,r);
}
long long query(int i,long long x,long long y)
{
long long ans=-inf;
yts2 o;
o.x=x;o.y=y;
if (y>=0)
{
int l=1,r=t[i].sizeup;
while (r-l>=3)
{
int mid=l+(r-l)/3,midmid=r-(r-l)/3;
if ((o^p[t[i].up[mid]])>(o^p[t[i].up[midmid]])) r=midmid; else l=mid;
}
for (int j=l;j<=r;j++) ans=max(ans,o^p[t[i].up[j]]);
}
else
{
int l=1,r=t[i].sizedw;
while (r-l>=3)
{
int mid=l+(r-l)/3,midmid=r-(r-l)/3;
if ((o^p[t[i].dw[mid]])>(o^p[t[i].dw[midmid]])) r=midmid; else l=mid;
}
for (int j=l;j<=r;j++) ans=max(ans,o^p[t[i].dw[j]]);
}
return ans;
}
void build(int i)
{
int size=0;
for (int j=t[i].l;j<=t[i].r;j++) tmp[++size]=j;
sort(tmp+1,tmp+size+1,cmp);
t[i].sizeup=0;t[i].sizedw=0;
for (int j=1;j<=size;j++)
{
while (t[i].sizeup>1 && (p[tmp[j]]-p[t[i].up[t[i].sizeup]])*(p[t[i].up[t[i].sizeup]]-p[t[i].up[t[i].sizeup-1]])<=0) t[i].sizeup--;
t[i].up[++t[i].sizeup]=tmp[j];
while (t[i].sizedw>1 && (p[tmp[j]]-p[t[i].dw[t[i].sizedw]])*(p[t[i].dw[t[i].sizedw]]-p[t[i].dw[t[i].sizedw-1]])>=0) t[i].sizedw--;
t[i].dw[++t[i].sizedw]=tmp[j];
}
}
long long query(int i,int l,int r,long long x,long long y)
{
if (l<=t[i].l && t[i].r<=r)
{
if (!t[i].flag) t[i].flag=1,build(i);
return query(i,x,y);
}
int mid=(t[i].l+t[i].r)/2;
long long ans=-inf;
if (l<=mid) ans=max(ans,query(i*2,l,r,x,y));
if (mid<r) ans=max(ans,query(i*2+1,l,r,x,y));
return ans;
}
int main()
{
scanf("%d%s",&T,s1);
for (int i=1;i<=T;i++)
{
scanf("%s",s);
scanf("%d%d",&q[i].x,&q[i].y);
if (s[0]=='A') q[i].op=1,n++;
else
{
q[i].op=2;
scanf("%d%d",&q[i].l,&q[i].r);
}
}
build(1,1,n);
for (int i=1;i<=T;i++)
{
if (s1[0]!='E') q[i].x=decode(q[i].x,ans),q[i].y=decode(q[i].y,ans);
if (q[i].op==1) p[++tot].x=q[i].x,p[tot].y=q[i].y;
else
{
q[i].l=decode(q[i].l,ans);q[i].r=decode(q[i].r,ans);
ans=query(1,q[i].l,q[i].r,q[i].x,q[i].y);
printf("%lld\n",ans);
}
}
return 0;
}