```cpp
#include <bits/stdc++.h>
using namespace std;
#define _rep(i_,a_,b_) for(int i_ = (a_); i_ <= (b_); ++i_)
#define mid ((L+R) >> 1)
#define multiCase() int testCnt = in(); _rep(curCase,1,testCnt)
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
int in(void) { int x; scanf("%d", &x); return x; } ll inl(void) { ll x; scanf("%lld", &x); return x; }
void out(int x) { printf("%d ", x); } void outln(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld ", x); } void outln(ll x) { printf("%lld\n", x); }
template<typename T> void chkmax(T &a, const T &b) { a = max(a, b); }
template<typename T> void chkmin(T &a, const T &b) { a = min(a, b); }
const int kN = 400500; const ll kInf = numeric_limits<ll>::max();
struct Line { int k, b; };
Line t[kN];
bool operator < (const Line &a, const Line &b) { return a.k != b.k ? a.k < b.k : a.b < b.b; }
struct Hull_mx { //查询的是交点最大值
vector<Line> s;
void insert(Line l) { s.push_back(l); }
void build(int n) {
sort(t + 1, t + 1 + n);
auto check = [](Line fix, Line a, Line b) -> bool
{ return ll(a.b - fix.b) * (fix.k - b.k) >= ll(b.b - fix.b) * (fix.k - a.k); };
_rep(i,1,n) { Line &l = t[i];
if(!s.empty() && l.k == s.back().k) {
if(l.b > s.back().b) s.pop_back();
else continue;
}
while(s.size() > 1 && check(s[s.size() - 2], s.back(), l)) s.pop_back();
s.push_back(l);
}
}
ll query(int x, int y) {
int L = 0, R = s.size() - 1; ll ans = -kInf;
while(L <= R) {
ll f = 1ll * s[mid].k * x + 1ll * s[mid].b * y; chkmax(ans, f);
if(mid != 0 && 1ll * s[mid - 1].k * x + 1ll * s[mid - 1].b * y > f) R = mid - 1;
else L = mid + 1;
}
return ans;
}
};
//Segment Tree
Hull_mx tmx[kN << 2], tneg[kN << 2]; Line l1, l2;
void insert(int x, int L, int R, int pos) {
if(L == R) { tmx[x].insert(l1), tneg[x].insert(l2); return; }
if(pos <= mid) insert(x << 1, L, mid, pos);
else insert(x << 1 | 1, mid + 1, R, pos);
if(pos == R) {
int n = 0;
for(Line l1 : tmx[x << 1].s) t[++n] = l1;
for(Line l2 : tmx[x << 1 | 1].s) t[++n] = l2;
tmx[x].build(n);
n = 0;
for(Line l1 : tneg[x << 1].s) t[++n] = l1;
for(Line l2 : tneg[x << 1 | 1].s) t[++n] = l2;
tneg[x].build(n);
}
}
ll queryMax(int x, int L, int R, int l, int r, int qx, int qy) {
if(l <= L && R <= r) return tmx[x].query(qx, qy);
ll res = -kInf;
if(l <= mid) chkmax(res, queryMax(x << 1, L, mid, l, r, qx, qy));
if(mid < r) chkmax(res, queryMax(x << 1 | 1, mid + 1, R, l, r, qx, qy));
return res;
}
ll queryNeg(int x, int L, int R, int l, int r, int qx, int qy) {
if(l <= L && R <= r) return tneg[x].query(qx, qy);
ll res = -kInf;
if(l <= mid) chkmax(res, queryNeg(x << 1, L, mid, l, r, qx, qy));
if(mid < r) chkmax(res, queryNeg(x << 1 | 1, mid + 1, R, l, r, qx, qy));
return res;
} int history[kN];
int isEnc; ll lastans;
int decode(int x) { return isEnc ? (x ^ (lastans & 0x7fffffff)) : x; }
int main() {
int n = in(); char isEncode[5]; scanf("%s", isEncode); isEnc = isEncode[0] == 'A';
int m = 0;
_rep(i,1,n) {
char cmd[5]; scanf("%s", cmd);
//ans = x0qx + y0qy
//ans / qy = x0(qx/qy) + y0
if(cmd[0] == 'A') {
++m;
int x = decode(in()), y = decode(in()); history[m] = x;
l1 = Line{x, y}; l2 = Line{-x, -y};
insert(1, 1, n, m);
} else {
int x = decode(in()), y = decode(in()); int l = decode(in()), r = decode(in());
if(y == 0) {
ll ans = -kInf;
_rep(j,l,r) chkmax(ans, 1ll * x * history[j]);
printf("%lld\n", lastans = ans);
continue;
}
ll res = y > 0 ? queryMax(1, 1, n, l, r, x, y) : queryNeg(1, 1, n, l, r, -x, -y);
printf("%lld\n", lastans = res);
}
}
return 0;
}
```
by fjy666 @ 2023-03-13 13:43:31