记录编号	396886	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]向量vec	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.637 s
提交时间	2017-04-19 13:03:06	内存使用	11.74 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
typedef long long ll;
typedef double db;
struct pt{
	ll x,y;
	pt(ll X=0,ll Y=0){x=X;y=Y;}
	ll operator * (const pt a){return x*a.x+y*a.y;}
};
db k(pt a,pt b){
	if (a.x==b.x) return a.y<b.y?1e9:-1e9;
	return db(a.y-b.y)/(a.x-b.x);
}
struct convex_hall{
	pt a[N];int tl;db K[N];
	void init(){tl=0;}
	void ins(pt v){
		for (;tl>1&&K[tl-1]<k(a[tl],v);tl--);
		K[tl]=k(a[tl],v);
		a[++tl]=v;
	}
	ll query(pt v){
		int l=1,r=tl;
		if (l>r) return -1e16;
		while (l<r){
			int mid=(l+r)>>1;
			if (a[mid]*v>a[mid+1]*v) r=mid;else l=mid+1;
		}
		return a[l]*v;
	}
}V;
ll ans[N];
int n,vis[N],tp[N],x[N],y[N],ID[N],q[N],size;
bool cmp(int a,int b){return x[a]<x[b];}
void solve(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	sort(q+l,q+mid+1,cmp);
	V.init();
	for (int i=l;i<=mid;i++){
		int id=q[i];
		if (tp[id]==1) V.ins(pt(x[id],y[id]));
	}
	for (int i=mid+1;i<=r;i++){
		int id=q[i];
		if (tp[id]==3) ans[id]=max(ans[id],V.query(pt(x[id],y[id])));
	}
}
void cdq(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	static int C=0;++C;
	for (int i=l;i<=r;i++)
		if (tp[i]==2) vis[ID[i]]=C;
	size=0;
	for (int i=l;i<=mid;i++)
	if (tp[i]==1){
		int id=ID[i];
		if (vis[id]!=C) q[++size]=i;else vis[id]=-C;
	}
	for (int i=r;i>mid;i--){
		int id=ID[i];
		if (tp[i]==3) q[++size]=i;
		if (tp[i]==2&&vis[id]==-C) q[++size]=id;
	}
	if (size) solve(1,size);
}
int que[N],cnt;
int main()
{
	freopen("vec.in","r",stdin);
	freopen("vec.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		ID[i]=i;
		scanf("%d",&tp[i]);
		if (tp[i]==1||tp[i]==3) scanf("%d%d",&x[i],&y[i]);
			else scanf("%d",&ID[i]),ID[i]=que[ID[i]];
		if (tp[i]==1) que[++cnt]=i;
	}
	cdq(1,n);
	for (int i=1;i<=n;i++)
		if (tp[i]==3) printf("%lld\n",ans[i]);
	return 0;
}