C++11(clang++ 3.9) 解法, 执行用时: 1292ms, 内存消耗: 152264K, 提交时间: 2019-03-16 11:23:14

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long LL;

const int N=400005;
const LL inf=100000000000000000;

int n,tot,que[N];
pair<int,int> tmp[N],a[N];
struct tree{vector<pair<int,int> > u,d;}t[N*5];
LL ans;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

inline int decode(int x,LL ans)
{
    return x^(ans&0x7fffffff);
}

double get_k(pair<int,int> x,pair<int,int> y)
{
    return (double)(x.second-y.second)/(x.first-y.first);
}

void build(int d,int l,int r)
{
    int tot=0;
    for (int i=l;i<=r;i++) tmp[++tot]=a[i];
    sort(tmp+1,tmp+tot+1);
    for (int i=tot;i>1;i--) if (tmp[i].first==tmp[i-1].first) tmp[i-1].second=tmp[i].second;
    tot=unique(tmp+1,tmp+tot+1)-tmp-1;
    int head=1,tail=1;que[1]=1;
    for (int i=2;i<=tot;i++)
    {
        while (head<tail&&get_k(tmp[que[tail-1]],tmp[que[tail]])<get_k(tmp[que[tail]],tmp[i])) tail--;
        que[++tail]=i;
    }
    while (head<=tail) t[d].u.push_back(tmp[que[head]]),head++;

    tot=0;
    for (int i=l;i<=r;i++) tmp[++tot]=a[i];
    sort(tmp+1,tmp+tot+1);
    for (int i=1;i<tot;i++) if (tmp[i].first==tmp[i+1].first) tmp[i+1].second=tmp[i].second;
    tot=unique(tmp+1,tmp+tot+1)-tmp-1;
    head=1;tail=1;que[1]=1;
    for (int i=2;i<=tot;i++)
    {
        while (head<tail&&get_k(tmp[que[tail-1]],tmp[que[tail]])>get_k(tmp[que[tail]],tmp[i])) tail--;
        que[++tail]=i;
    }
    while (head<=tail) t[d].d.push_back(tmp[que[head]]),head++;
}

LL get_ans(pair<int,int> x,pair<int,int> y)
{
    return (LL)x.first*y.first+(LL)x.second*y.second;
}

LL query(int d,pair<int,int> p)
{
    int x=p.first,y=p.second;
    if (!y) return max(x*t[d].d[0].first,x*t[d].d[t[d].d.size()-1].first);
    if (y<0)
    {
        int l=0,r=t[d].d.size()-2;
        while (l<=r)
        {
            int mid=(l+r)/2;
            if (get_ans(t[d].d[mid],p)>get_ans(t[d].d[mid+1],p)) r=mid-1;
            else l=mid+1;
        }
        return get_ans(t[d].d[r+1],p);
    }
    else
    {
        int l=0,r=t[d].u.size()-2;
        while (l<=r)
        {
            int mid=(l+r)/2;
            if (get_ans(t[d].u[mid],p)>get_ans(t[d].u[mid+1],p)) r=mid-1;
            else l=mid+1;
        }
        return get_ans(t[d].u[r+1],p);
    }
}

void ins(int d,int l,int r,int x)
{
    if (r==x) build(d,l,r);
    if (l==r) return;
    int mid=(l+r)/2;
    if (x<=mid) ins(d*2,l,mid,x);
    else ins(d*2+1,mid+1,r,x);
}

LL query(int d,int l,int r,int x,int y,pair<int,int> p)
{
    if (x>y) return -inf;
    if (l==x&&r==y) return query(d,p);
    int mid=(l+r)/2;
    return max(query(d*2,l,mid,x,min(y,mid),p),query(d*2+1,mid+1,r,max(x,mid+1),y,p));
}

int main()
{
    n=read();
    char ty[2];scanf("%s",ty);
    for (int i=1;i<=n;i++)
    {
        char op[2];
        scanf("%s",op);
        if (op[0]=='A')
        {
            int x=read(),y=read();
            if (ty[0]!='E') x=decode(x,ans),y=decode(y,ans);
            a[++tot]=make_pair(x,y);
            ins(1,1,n,tot);
        }
        else
        {
            int x=read(),y=read(),l=read(),r=read();
            if (ty[0]!='E') x=decode(x,ans),y=decode(y,ans),l=decode(l,ans),r=decode(r,ans);
            printf("%lld\n",ans=query(1,1,n,l,r,make_pair(x,y)));
        }
    }
    return 0;
}