「SDOI2014」向量集

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

1. A x y ：加入向量 \((x, y)\)；
2. Q x y l r：询问第 \(L\) 个到第 \(R\) 个加入的向量与向量 \((x, y)\) 的点积的最大值。集合初始时为空。

对于所有的数据，\(1 \leq N \leq 4 \times 10^5\)，操作中的向量坐标满足 \(|x|,|y| \leq 10^8\)，询问满足 \(1 \leq L \leq R \leq T\)，其中 \(T\) 为已经加入的向量个数。

一眼上去，线段树套KD-树？？？

然后觉得4e5根本跑不动，就一直没写。

看了题解才知道自己还是对凸优化不够熟悉，明明感觉可以凸优化，但搞不清楚式子怎么化

一般的套路是，对一个值询问一个集合，找其中一个运算后得到最值之类的，我们这时候把那个集合给弄成点集，把询问搞成最大截距或者最大斜率，就可以在凸包上三分了。

这个题询问点是\((z,w)\)，即询问\(ans=xz+yw\)的最大值，化简一下就成了

最大化截距就讨论一下\(w\)的正负，决定在上or下凸包上三分就可以了。

然后我们需要支持动态插入凸包，可以直接在线段树上模拟二进制分组，每次给线段树的区间加点，当某个区间加满了点，就构建凸包（没加满是不会被询问的）

复杂度\(O(n\log^2 n)\)，LOJ上懒得卡了...

有个错误调了好久，以前写凸包的时候没注意，一定要以\(y\)作为第二关键字，否则在最右边的\(x\)上可能出现问题。

Code:

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

#define ll long long

const int N=4e5+10;

using std::max;

int n,m,flag;

template <class T>

void read(T &x)

{

    x=0;char c=getchar();bool f=0;

    while(!isdigit(c)) f=c=='-'?1:0,c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    x=f?-x:x;

}

inline int decode(int x,ll lastans){return flag?x^(lastans&0x7fffffff):x;}

struct Point

{

	ll x,y;

	Point(){}

	Point(ll X,ll Y){x=X,y=Y;}

	Point friend operator -(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}

	bool friend operator <(Point a,Point b){return a.x==b.x?a.y<b.y:a.x<b.x;}

};

ll Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}

std::vector<Point> pot[N<<2],s[N<<2];

int Endro[N<<2],endro;

void ins(Point x,int id)

{

	int tot=s[id].size()-1;

	while(tot>=endro&&Cross(s[id][tot]-s[id][tot-1],x-s[id][tot])<=0) --tot,s[id].pop_back();

	s[id].push_back(x);

}

void build(int id)

{

	std::sort(pot[id].begin(),pot[id].end());

	endro=1;

	for(int i=0;i<pot[id].size();i++)

        ins(pot[id][i],id);

	endro=s[id].size();

	Endro[id]=endro-1;

	for(int i=pot[id].size()-2;~i;i--) ins(pot[id][i],id);

}

#define ls id<<1

#define rs id<<1|1

void change(int id,int l,int r,int p,Point ins)

{

	pot[id].push_back(ins);

	if(s[id].empty()&&pot[id].size()==r+1-l) build(id);

	if(l==r) return;

	int mid=l+r>>1;

	if(p<=mid) change(ls,l,mid,p,ins);

	else change(rs,mid+1,r,p,ins);

}

ll cal(int x,int y,Point d)

{

	return d.x*x+d.y*y;

}

ll yuu(int id,int x,int y)

{

	int endro=s[id].size()-1;

	if(y==0) return max(s[id][0].x*x,s[id][Endro[id]].x*x);

	int l,r;

	if(y>0) l=Endro[id],r=endro;

	else l=0,r=Endro[id];

	while(l<r)

	{

		int mid=l+r>>1;

		if(cal(x,y,s[id][mid])<cal(x,y,s[id][mid+1])) l=mid+1;

		else r=mid;

	}

	return cal(x,y,s[id][l]);

}

ll query(int id,int L,int R,int l,int r,int x,int y)

{

	if(l==L&&r==R) return yuu(id,x,y);

	int Mid=L+R>>1;

	if(r<=Mid) return query(ls,L,Mid,l,r,x,y);

	else if(l>Mid) return query(rs,Mid+1,R,l,r,x,y);

	else return max(query(ls,L,Mid,l,Mid,x,y),query(rs,Mid+1,R,Mid+1,r,x,y));

}

int main()

{

	char op[10];read(n),scanf("%s",op);

	if(op[0]!='E') flag=1;

	ll las=0;

	for(int x,y,l,r,i=1;i<=n;i++)

	{

		scanf("%s",op);

		if(op[0]=='A')

		{

		    read(x),read(y);

			x=decode(x,las),y=decode(y,las);

			change(1,1,n,++m,Point(x,y));

		}

		else

		{

		    read(x),read(y),read(l),read(r);

			x=decode(x,las),y=decode(y,las);

			l=decode(l,las),r=decode(r,las);

			printf("%lld\n",las=query(1,1,n,l,r,x,y));

		}

	}

	return 0;

}