题目描述

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

"A x y (|x|，|y| < =10^8)"：加入向量(x，y);

"Q x y l r (|x|，|y| < =10^8，1 < =L < =R < =T，其中T为已经加入的向量个数)"：询问第L个到第R个加入的向量与向量(x，y)的点积的最大值。

集合初始时为空。

输入

输入的第一行包含整数N和字符s，分别表示操作数和数据类别；

接下来N行，每行一个操作，格式如上所述。

请注意s≠'E'时，输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入：

inline int decode (int x long long lastans) {

     return x ^ (lastans & Ox7fffffff);

}

其中x为程序读入的数，lastans为之前最后一次询问的答案。在第一次询问之前，lastans=0。

注：向量(x，y)和(z，w)的点积定义为xz+yw。

输出

对每个Q操作，输出一个整数表示答案。

样例输入

6 A

A 3 2

Q 1 5 1 1

A 15 14

A 12 9

Q 12 8 12 15

Q 21 18 19 18

样例输出

13

17

17

---

题解

线段树+STL-vector维护凸包

本质是什么呢：给出 $x_0$ 和 $y_0$ ，求满足条件的 $x,y$ 使得 $x_0x+y_0y$ 最大。

我们不妨设这个值是 $c$ ，则要最大化 $c$ 。

当 $y>0$ 时：

给这个式子 $c=x_0x+y_0y$ 变形，得：$y=-\frac {x_0}{y_0}x+\frac c{y_0}$ 。想要 $c$ 最大，即要 $\frac c{y_0}$ 最大。

相当于是一条斜率为 $-\frac{x_0}{y_0}$ 的直线，要使纵截距最大，答案一定在上凸壳上，且所选点与答案形成单峰函数。

因此维护上凸壳，在凸壳上二分即可。

$y<0$ 的情况同理，维护下凸壳并二分即可。$y=0$ 的情况只要求 $x$ 最大/小，在两个凸壳上二分都可以。

考虑使用线段树维护一段区间的凸壳。

由于强制在线，因此不能提前求凸壳。但我们可以发现：如果线段树的一个节点没有被全部加入（即没加全），那么这个点一定不会出现在询问区间中。因此我们在线段树上插入，当且仅当 $tot==r$ 时，对该节点建立上凸壳即可。

时间复杂度 $O(n\log^2 n)$ 

#include 
     
      #include 
      
       #include 
       
        #define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;typedef long long ll;struct point{	ll x , y;	point() {}	point(ll a , ll b) {x = a , y = b;}	ll operator*(const point &a)const {return x * a.x + y * a.y;}	ll operator^(const point &a)const {return x * a.y - y * a.x;}	point operator-(const point &a)const {return point(x - a.x , y - a.y);}	bool operator<(const point &a)const {return x == a.x ? y < a.y : x < a.x;}};vector
        
          t[1600010] , v1[1600010] , v2[1600010];char opt[5] , str[5];void insert(int p , point o , int l , int r , int x){	t[x].push_back(o);	if(p == r)	{		sort(t[x].begin() , t[x].end());		int i;		for(i = 0 ; i <= r - l ; i ++ )		{			while(v1[x].size() > 1 && ((t[x][i] - v1[x][v1[x].size() - 1]) ^ (v1[x][v1[x].size() - 2] - v1[x][v1[x].size() - 1])) >= 0) v1[x].pop_back();			v1[x].push_back(t[x][i]);			while(v2[x].size() > 1 && ((t[x][i] - v2[x][v2[x].size() - 1]) ^ (v2[x][v2[x].size() - 2] - v2[x][v2[x].size() - 1])) <= 0) v2[x].pop_back();			v2[x].push_back(t[x][i]);		}	}	if(l == r) return;	int mid = (l + r) >> 1;	if(p <= mid) insert(p , o , lson);	else insert(p , o , rson);}ll query1(int b , int e , point o , int l , int r , int x){	if(b <= l && r <= e)	{		int L = 1 , R = v1[x].size() - 1 , Mid , Ans = 0;		while(L <= R)		{			Mid = (L + R) >> 1;			if(o * v1[x][Mid] > o * v1[x][Mid - 1]) Ans = Mid , L = Mid + 1;			else R = Mid - 1;		}		return o * v1[x][Ans];	}	int mid = (l + r) >> 1;	ll ans = -1ll << 62;	if(b <= mid) ans = max(ans , query1(b , e , o , lson));	if(e > mid) ans = max(ans , query1(b , e , o , rson));	return ans;}ll query2(int b , int e , point o , int l , int r , int x){	if(b <= l && r <= e)	{		int L = 1 , R = v2[x].size() - 1 , Mid , Ans = 0;		while(L <= R)		{			Mid = (L + R) >> 1;			if(o * v2[x][Mid] > o * v2[x][Mid - 1]) Ans = Mid , L = Mid + 1;			else R = Mid - 1;		}		return o * v2[x][Ans];	}	int mid = (l + r) >> 1;	ll ans = -1ll << 62;	if(b <= mid) ans = max(ans , query2(b , e , o , lson));	if(e > mid) ans = max(ans , query2(b , e , o , rson));	return ans;}int main(){	int n , tot = 0 , i , l , r;	ll last = 0;	point o;	scanf("%d%s" , &n , opt);	for(i = 1 ; i <= n ; i ++ )	{		scanf("%s%lld%lld" , str , &o.x , &o.y) , o.x ^= last , o.y ^= last;		if(str[0] == 'A') insert(++tot , o , 1 , n , 1);		else		{			scanf("%d%d" , &l , &r) , l ^= last , r ^= last;			if(o.y > 0) last = query1(l , r , o , 1 , n , 1);			else last = query2(l , r , o , 1 , n , 1);			printf("%lld\n" , last) , last &= 0x7fffffff;			if(opt[0] == 'E') last = 0;		}	}	return 0;}