Description

要求一个数据结构，支持：

A：在容器末尾插入一个向量(x,y)

Q：询问容器(l,r)的区间里的所有向量，与向量(x,y)点积最大的是多少

操作数N在4*10^5范围内，保证答案在64位整数范围内，强制在线

A类数据：30分，N<=1000

B类数据：10分，插入向量横坐标单增且总是询问整个区间

C类数据：20分，插入向量坐标单增

D类数据：10分，总是询问整个区间

E类数据：20分，离线

F类数据：10分，无特殊条件

Solution

答案显然是在凸包上的（随便写一写方程大概就明白了），于是我们在凸包(壳)上二(三)分。

大概有好多方法可以解决这个问题。

A类数据暴力，B、C类数据分块，D类数据平衡树套凸包，E类数据分治。

这样是有80~90分的，如果你在考场上的代码能力爆表的话= =

正解我知道的有二进制分组和树套树两个方法。

二进制分组：O(Nlg^2N)每一个结点i储存到该结点之前的距离为1,2,4...lowbit(i)大小的区间所构成的凸包

这样每次插入的复杂度是O(f(lowbit(i)))的，询问时，显然可以将一个区间分割成logN块，复杂度是O(log^2N)的

我用的是树套树，线段树套平衡树维护凸包

每次插入的时候我们在区间里所在的动态凸包里插入一个点O(log^2N)，询问的时候和普通询问是一样的O(log2^N)

但是由于普通平衡树常数非常巨大= =所以我刚开始写的平衡树就TLE了，然后玩了许久的常数后还是没用，所以换成SBT就跑得飞快地过掉了。。这样编程复杂度显然是巨大的。。。要写平衡树维护动态凸包，还要写在平衡树维护的凸包上的二分，最后还要套上线段树。。

所以还有一种线段树套数组的方法

每次插入的时候假如已经把该区间里的所有点都加入过了，那么我们暴力建立这个区间的凸包。询问时，如果该区间是完整的就可以询问，否则继续往下走。什么？不能保证询问是O(lgN)的？那把线段树的长度开成2的幂次的大小就是了。。常数还是巨大。。因为内存要动态开。。而windows下New是非常慢的。。所以linux下轻松过掉了。。但是Windows里TLE成狗（不要用Windows）写个内存池的话在Windows下也就过了吧。。

#include<cstdio>
#include<algorithm>
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
inline LL Dot(pii a, pii b) { return (LL) a.F * b.F + (LL) a.S * b.S; }
inline LL Xot(pii c, pii a, pii b) { return (LL) (a.F - c.F) * (b.S - c.S) - (LL) (a.S - c.S) * (b.F - c.F); }
char buf[25000000], *buff = buf;
namespace TIT
{
	const LL inf = 1LL << 60; pii V[400010]; int T;
	struct Tkey
	{
		int num, cnt, tot; pii *up, *dw, *st;
		inline void Clear() { num = cnt = tot = 0; up = dw = st = 0x0; }
		inline void Init(int N) { st = new pii[N+10]; up = new pii[N+10]; dw = new pii[N+10]; }
		inline void Make(int L, int R)
		{
			Init(R - L + 1); for(int i = L; i <= R; ++i) st[num++] = V[i]; sort(st, st + num);
			for(int i = 0; i < num; ++i)
			{
				while(cnt > 1 && Xot(up[cnt-1], up[cnt], st[i]) >= 0) --cnt; up[++cnt] = st[i];
				while(tot > 1 && Xot(dw[tot-1], dw[tot], st[i]) <= 0) --tot; dw[++tot] = st[i];
			}
		}
		inline LL Ask(int _l, int _r, pii now, pii *st)
		{
			LL ret = -inf; int l = _l, r = _r;
			while(r - l > 2)
			{
				int M = (l + r) / 2, U = M+1;
				LL temp1 = Dot(st[M], now);
				LL temp2 = Dot(st[U], now);
				if(temp1 > temp2)
					r = M, ret = max(ret, temp1); 
				else
					l = U, ret = max(ret, temp2);
			}
			for(int i = l; i <= r; ++i) ret = max(ret, Dot(st[i], now));
			if(_l == l && r != _r) ret = max(ret, Dot(st[_r], now));
			if(_r == r && l != _l) ret = max(ret, Dot(st[_l], now));
			return ret;
		}
		LL Query(pii now) { return now.S > 0 ? Ask(1, cnt, now, up) : Ask(1, tot, now, dw); }
	};
	struct Ttree
	{
		Tkey *p; int L, R, s; Ttree *lch, *rch;
		inline void Init(int l, int r)
		{
			(p = new Tkey()) -> Clear();
			lch = rch = 0x0; s = 0;
			int mid = ((L = l) + (R = r)) / 2;
			if(L == R) return; 
			(lch = new Ttree()) -> Init(L, mid);
			(rch = new Ttree()) -> Init(mid + 1, R);
		}
		inline void Modify(int pos, pii y)
		{
			int mid = (L + R) / 2;
			if((++s) == R-L+1) p -> Make(L, R); if(L == R) return;
			if(pos <= mid) lch -> Modify(pos, y); else rch-> Modify(pos, y);
		}
		inline LL Query(int l, int r, pii y)
		{
			int mid = (L + R) / 2;
			if(L == l && R == r && s == R-L+1) return p->Query(y);
			if(l > mid) return rch -> Query(l, r, y); else
			if(r <=mid) return lch -> Query(l, r, y); else
			return max(lch->Query(l, mid, y), rch->Query(mid+1, r, y));
		}
	} Tree;
	struct Tque { char o; int a, b, l, r; } Q[400010]; int M; LL lastans;
	inline int read(int &x)
	{
		x = 0; bool f = 0;
		while (*buff > '9' || *buff < '0') if(*(buff++) == '-') f = 1;
		while (*buff >='0' && *buff <='9') x = x * 10 + *buff ++ -48;
		return f ? (x = -x) : x;
	}
	inline void read(char x[])
	{
		x[0] = x[1] = x[2] = 0x0; int len = 0;
		while (*buff < 'A' || *buff > 'Z') ++buff;
		while (*buff >='A' && *buff <='Z') x[len++] = *buff++;
	}
	inline void Decode(int &x, LL lastans) { x = (x ^ (lastans & 0x7fffffff)); }
	void Solve()
	{
		fread(buf, 1, 25000000, stdin);
		int N; char s[10]; read(N); read(s);
		for(int i = 1; i <= N; ++i)
		{
			char ord[4]; read(ord); read(Q[i].a); read(Q[i].b);
			if((Q[i].o = ord[0]) == 'A') ++M; else read(Q[i].l), read(Q[i].r);
		}
		int Lim = 1; while(Lim < M) Lim *= 2; Tree.Init(1, Lim);
		for(int i = 1, a, b, l, r; i <= N; ++i)
		{
			char ord = Q[i].o; a = Q[i].a; b = Q[i].b;
			if(s[0] != 'E') Decode(a, lastans), Decode(b, lastans);
			pii now = make_pair(a, b); 
			if(ord == 'A') V[++T] = now, Tree.Modify(T, now); else
			{
				l = Q[i].l; r = Q[i].r;
				if(s[0] != 'E') Decode(l, lastans), Decode(r, lastans);
				printf("%I64d\n", lastans = Tree.Query(l, r, now));
			}
		}
	}
}
int main()
{
	freopen("vset.in", "r", stdin);
	freopen("vset.out", "w", stdout);
	TIT::Solve();
	return 0;
}