【SDOI2014】向量集

题目描述

我们分析一波：

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

\[A\cdot x_i+B\cdot y_i>A\cdot x_j+B\cdot y_j\\
A\cdot(x_i-x_j)>B\cdot(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-l\geq 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))<<"\n";

		}

	}

	return 0;

}

巴特西

【SDOI2014】向量集

【SDOI2014】向量集

最新文章

热门文章