首页 > 代码库 > bzoj3533: [Sdoi2014]向量集
bzoj3533: [Sdoi2014]向量集
Description
维护一个向量集合，在线支持以下操作：
"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)的点积的最大值。
集合初始时为空。
Input
输入的第一行包含整数N和字符s，分别表示操作数和数据类别；
接下来N行，每行一个操作，格式如上所述。
请注意s≠‘E‘时，输入中的所有整数都经过了加密。你可以使用以下程序
得到原始输入：
inline int decode (int x long long lastans) {
return x ^ (lastans & Ox7fffffff);
}
function decode
begin
其中x为程序读入的数，lastans为之前最后一次询问的答案。在第一次询问之前，lastans=0。
注：向量(x，y)和(z，W)的点积定义为xz+yw。
Output
对每个Q操作，输出一个整数表示答案。
将向量看作平面上的点，线段树维护上、下凸包，在凸包上三分可得到最优解。对线段树的每个区间，当区间内向量都已读入时计算凸包。
#include<cstdio>#include<algorithm>typedef long long i64;char buf[5000000],*ptr=buf,*pmx=buf+5000000;const i64 inf=1ll<<62;const int N=1e7;int g(){ if(ptr==pmx)fread(ptr=buf,1,5000000,stdin); return *ptr++;}int _(){ int x=0,f=1,c=g(); while(c<48||c>57)c==‘-‘&&(f=-1),c=g(); while(c>47&&c<58)x=x*10+c-48,c=g(); return x*f;}int _c(){ int c=g(); while(c<‘A‘||c>‘Z‘)c=g(); return c;}void maxs(i64&a,i64 b){if(a<b)a=b;}void maxs(int&a,int b){if(a<b)a=b;}void mins(int&a,int b){if(a>b)a=b;}struct pos{ int x,y; i64 operator()(pos a){ return i64(x)*a.x+i64(y)*a.y; }}mem[21000007],*mp=mem;pos operator-(pos a,pos b){ return (pos){a.x-b.x,a.y-b.y};}i64 operator*(pos a,pos b){ return i64(a.x)*b.y-i64(a.y)*b.x;}bool operator<(pos a,pos b){ return a.x!=b.x?a.x<b.x:a.y<b.y;}struct node{ pos*l,*r; void init(int x,int y){ l=mp; *mp++=(pos){x,y}; r=mp; } void ins(pos x){ if(mp>l&&mp[-1].x==x.x)--mp; while(mp-l>=2&&(x-mp[-1])*(mp[-2]-mp[-1])>=0)--mp; *mp++=x; } void init(node a,node b){ if(!a.l)*this=b; else if(!b.l)*this=a; else{ l=mp; pos*ap=a.l,*bp=b.l; while(ap!=a.r&&bp!=b.r){ if(*ap<*bp)ins(*ap++); else ins(*bp++); } while(ap!=a.r)ins(*ap++); while(bp!=b.r)ins(*bp++); r=mp; } } i64 find(pos x){ if(!l)return -1ll<<62; i64 v1,v2; int L=0,R=r-l-1,M1,M2; while(R-L>3){ M1=L+R>>1; M2=M1+1; if(x(l[M1])<x(l[M2]))L=M1; else R=M2; } for(v1=x(l[L++]);L<=R;++L)maxs(v1,x(l[L])); return v1; }}us[1051111],ds[1051111];bool d[1051111];int n,de,la=0,x,y,l,r,id=0;int main(){ n=_();de=_c()!=‘E‘; for(int i=0;i<n;++i){ if(_c()==‘A‘){ x=_();y=_();++id; if(de)x^=la,y^=la; int w=id+524288; us[w].init(x,y); ds[w].init(x,-y); d[w]=1; for(w>>=1;w&&d[w<<1^1];w>>=1){ us[w].init(us[w<<1],us[w<<1^1]); ds[w].init(ds[w<<1],ds[w<<1^1]); d[w]=1;d[w<<1^1]=0; } }else{ x=_();y=_();l=_();r=_(); if(de)x^=la,y^=la,l^=la,r^=la; i64 ans=-1ll<<62; pos p1=(pos){x,y},p2=(pos){x,-y}; for(l+=524287,r+=524289;l^r^1;l>>=1,r>>=1){ if(~l&1)maxs(ans,us[l^1].find(p1)),maxs(ans,ds[l^1].find(p2)); if(r&1)maxs(ans,us[r^1].find(p1)),maxs(ans,ds[r^1].find(p2)); } printf("%lld\n",ans); la=ans&0x7fffffff; } } return 0;}
bzoj3533: [Sdoi2014]向量集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。