【SDOI2014】向量集

【SDOI2014】向量集

题目描述

我们分析一波：

假设我们询问((A,B))，(x_i>x_j)若

[Acdot x_i+Bcdot y_i>Acdot x_j+Bcdot y_j\ Acdot(x_i-x_j)>Bcdot(y_j-y_i) ]

当(B>0)

[-frac{A}{B}<frac{y_i-y_j}{x_i-x_j} ]

否则

[-frac{A}{B}>frac{y_i-y_j}{x_i-x_j} ]

所以，对于(B>0)，我们在上凸壳上三分，否则在下凸壳上三分。(B=0)随意。

三分细节：条件是(r-lgeq 3)，然后两个端点是(frac{l+l+r}{3})以及(frac{l+r+r}{3})。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1e16
#define eps 1e-7
#define N 400005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n;
ll ans;
char type;
int decode(int x) {return (type!='E')?x^(ans&0x7fffffff):x;}

struct point {
	double x,y;
	bool operator <(const point &a)const {return x<a.x;}
};

double slope(const point &a,const point &b) {
	if(fabs(a.x-b.x)<eps) return a.y<b.y?inf:-inf;
	return (a.y-b.y)/(a.x-b.x);
}
double cdot(const point &a,const point &b) {return a.x*b.x+a.y*b.y;}

vector<point>tem;
struct Convex {
	vector<point>st;
	int size() {return st.size();}
	void Insert(point a) {st.push_back(a);}
	void build(int flag) {
		sort(st.begin(),st.end());
		tem.clear();
		if(flag) {
			//上凸壳 
			for(int i=0;i<st.size();i++) {
				while(tem.size()>1&&slope(tem[tem.size()-2],tem[tem.size()-1])<slope(tem[tem.size()-1],st[i])+eps) tem.pop_back();
				tem.push_back(st[i]);
			}
		} else {
			//下凸壳 
			for(int i=0;i<st.size();i++) {
				while(tem.size()>1&&slope(tem[tem.size()-2],tem[tem.size()-1])+eps>slope(tem[tem.size()-1],st[i])) tem.pop_back();
				tem.push_back(st[i]);
			}
		}
		st=tem;
	}
	ll query(point a) {
		int l=0,r=st.size()-1;
		while(r-l>=3) {
			int lmid=(l+l+r)/3;
			int rmid=(l+r+r)/3;
			if(cdot(st[lmid],a)>cdot(st[rmid],a)) r=rmid;
			else l=lmid;
		}
		double ans=-inf;
		for(;l<=r;l++) ans=max(ans,cdot(st[l],a));
		return (ll)ans;
	}
};
struct tree {
	int l,r;
	Convex u,d;
}tr[N<<2];
void build(int v,int l,int r) {
	tr[v].l=l,tr[v].r=r;
	if(l==r) return ;
	int mid=l+r>>1;
	build(v<<1,l,mid),build(v<<1|1,mid+1,r);
}
void Insert(int v,int p,point a) {
	tr[v].u.Insert(a);
	tr[v].d.Insert(a);
	if(tr[v].u.size()==tr[v].r-tr[v].l+1) {
		tr[v].u.build(1);
		tr[v].d.build(0);
	}
	if(tr[v].l==tr[v].r) return ;
	int mid=tr[v].l+tr[v].r>>1;
	if(p<=mid) Insert(v<<1,p,a);
	else Insert(v<<1|1,p,a);
}
ll query(int v,int l,int r,point a) {
	if(tr[v].l>r||tr[v].r<l) return -inf;
	if(l<=tr[v].l&&tr[v].r<=r) return a.y>0?tr[v].u.query(a):tr[v].d.query(a);
	return max(query(v<<1,l,r,a),query(v<<1|1,l,r,a));
}
int main() {
	n=Get();
	scanf("%c",&type);
	build(1,1,n);
	char op;
	point a;
	int l,r;
	int now=0;
	while(n--) {
		while(op=getchar(),!isalpha(op));
		if(op=='A') {
			now++;
			a.x=decode(Get()),a.y=decode(Get());
			Insert(1,now,a);
		} else {
			a.x=decode(Get()),a.y=decode(Get());
			l=decode(Get()),r=decode(Get());
			cout<<(ans=query(1,l,r,a))<<"
";
		}
	}
	return 0;
}