Description：

维护一个向量集合，在线支持以下操作：

加入向量 $(x,y)$ ，询问第 $L$ 个到第 $R$ 个加入的向量与向量 $(x,y)$ 的点积的最大值。

$1\le n \le 4\times 10^5$

Solution：

建一棵线段树，那么问题就变成了查询一段区间内与向量 $(x,y)$ 的点积的最大值，设这个向量为 $(x',y')$ ，那么要求最大化 $f=xx'+yy'$ ，移项得 $yy'=-xx'+f$ ，两边同除 $y$ 得 $y'=-\frac x yx'+\frac f y$ ，于是就变成了一条斜率为 $-\frac x y$ 的直线当经过哪个点时截距最小 $/$ 最大，可以维护上下凸壳在凸包上二分，偷懒可以写三分而且没有精度问题，但问题是我们不能每一次操作都合并从根到叶子的一条链上的所有点的凸包，于是可以每次加入一条线段时，判断一下线段树这个区间有没有被填满，因为只有填满的区间才会被询问到，每个区间只会合并一次，均摊 $O(n\log n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

int n;

#define MAXN 400010

#define NEG 0xc0c0c0c0c0c0c0c0

char getc()

{

    char c = getchar();

    while(!isupper(c))c = getchar();

    return c;

}

#define fi first

#define se second

typedef long long ll;

struct node

{

    int lc,rc;

    int siz;

    vector< pair<int,int> > v[2];

    node(){siz = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

    rt = newnode();

    if(l == r)return;

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    return;

}

double slope(pair<int,int> p1,pair<int,int> p2){return (double)(p1.se - p2.se) / (double)(p1.fi - p2.fi);}

pair<int,int> q[MAXN];

int top;

void merge(int rt)

{

    int lc = t[rt].lc,rc = t[rt].rc;

    top = 0;

    vector< pair<int,int> >::iterator i = t[lc].v[0].begin(),j = t[rc].v[0].begin();

    for(;i != t[lc].v[0].end() && j != t[rc].v[0].end();)

    {

        if((i -> fi) == (j -> fi)){if((i -> se) >= (j -> se))++j;else ++i;continue;}

        if((i -> fi) < (j -> fi)){while(top >= 2 && slope(*i,q[top]) >= slope(q[top],q[top - 1]))--top;q[++top] = *i;++i;}

        else{while(top >= 2 && slope(*j,q[top]) >= slope(q[top],q[top - 1]))--top;q[++top] = *j;++j;}

    }

    for(;i != t[lc].v[0].end();++i){while(top >= 2 && slope(*i,q[top]) >= slope(q[top],q[top - 1]))--top;q[++top] = *i;}

    for(;j != t[rc].v[0].end();++j){while(top >= 2 && slope(*j,q[top]) >= slope(q[top],q[top - 1]))--top;q[++top] = *j;}

    for(int i = 1;i <= top;++i)t[rt].v[0].push_back(q[i]);

    top = 0;

    i = t[lc].v[1].begin(),j = t[rc].v[1].begin();

    for(;i != t[lc].v[1].end() && j != t[rc].v[1].end();)

    {

        if(i -> fi == j -> fi){if(i -> se <= j -> se)++j;else ++i;continue;}

        if(i -> fi < j -> fi){while(top >= 2 && slope(*i,q[top]) <= slope(q[top],q[top - 1]))--top;q[++top] = *i;++i;}

        else{while(top >= 2 && slope(*j,q[top]) <= slope(q[top],q[top - 1]))--top;q[++top] = *j;++j;}

    }

    for(;i != t[lc].v[1].end();++i){while(top >= 2 && slope(*i,q[top]) <= slope(q[top],q[top - 1]))--top;q[++top] = *i;}

    for(;j != t[rc].v[1].end();++j){while(top >= 2 && slope(*j,q[top]) <= slope(q[top],q[top - 1]))--top;q[++top] = *j;}

    for(int i = 1;i <= top;++i)t[rt].v[1].push_back(q[i]);

    return;

}

void add(int rt,int p,int x,int y,int l,int r)

{

    if(l == r)

    {

        pair<int,int> p = make_pair(x,y);

        t[rt].v[0].push_back(p);

        t[rt].v[1].push_back(p);

        return;

    }

    if(p <= mid)add(t[rt].lc,p,x,y,l,mid);

    else add(t[rt].rc,p,x,y,mid + 1,r);

    if(p == r)merge(rt);

    return;

}

ll operator * (pair<int,int> a,pair<int,int> b)

{

    return ((ll)a.fi * b.fi + (ll)a.se * b.se);

}

void query(int rt,int x,int y,int L,int R,int l,int r,ll &ans)

{

    if(L <= l && r <= R)

    {

        pair<int,int> p = make_pair(x,y);

        if(y == 0)

        {

            ans = max(ans,max(t[rt].v[0][0] * p,t[rt].v[0][t[rt].v[0].size() - 1] * p));

            return;

        }

        int type = (y > 0 ? 0 : 1);

        int l = 0,r = t[rt].v[type].size() - 1;

        while(l <= r)

        {

            int d = (r - l) / 3,m1 = l + d,m2 = r - d;

            ans = max(ans,max(p * t[rt].v[type][m1],p * t[rt].v[type][m2]));

            if(p * t[rt].v[type][m1] < p * t[rt].v[type][m2])l = m1 + 1;

            else r = m2 - 1;

        }

        return;

    }

    if(L <= mid)query(t[rt].lc,x,y,L,R,l,mid,ans);

    if(R > mid)query(t[rt].rc,x,y,L,R,mid + 1,r,ans);

    return;

}

inline int decode(int x,long long lastans){return (x ^ (int)(lastans & 0x7fffffff));}

char opt;bool tag;

int main()

{

    scanf("%d",&n);opt = getc();

    if(opt != 'E')tag = true;else tag = false;

    build(root,1,n);

    char c;

    int x,y,l,r;

    int cur = 0;

    ll lastans = 0;

    for(int i = 1;i <= n;++i)

    {

        c = getc();

        if(c == 'A')

        {

            scanf("%d%d",&x,&y);

            if(tag)x = decode(x,lastans),y = decode(y,lastans);//cout << x << " " << y << endl;

            add(root,++cur,x,y,1,n);

        }

        else

        {

            scanf("%d%d%d%d",&x,&y,&l,&r);

            if(tag)x = decode(x,lastans),y = decode(y,lastans),l = decode(l,lastans),r = decode(r,lastans);

            ll ans = NEG;//cout << x << " " << y << " " << l << " " << r << endl;

            query(root,x,y,l,r,1,n,ans);

            printf("%lld\n",ans);

            lastans = ans;

        }

    }

    return 0;

}