bzoj3533【Sdoi2014】向量集

题目描述

维护一个向量集合，在线支持以下操作：
"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)的点积的最大值。
集合初始时为空

输入格式

输入的第一行包含整数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。

输出格式

对每个Q操作，输出一个整数表示答案。

提示

1 < =N < =4×10^5

新加数据一组..2015.315

题解
- 设当前向量为$(a,b)$集合中向量为$(x,y)$，设$z = ax+by$，有$y = - \frac{a}{b} x + \frac{z}{b}$
- 最优化$z$:
  - 当$b>0$即求过集合$S$中的某个点且斜率为$ - \frac{a}{b}$的直线$y$截距最大的为哪条，答案一定在上凸包上；
  - 同理$b<0$时求截距最小的为哪条；
  - $b==0$随便哪条查即可；
- 如果维护了区间$[L,R]$的凸包就可以在里面三分；
- 应该是可以用线段树套$splay$参照$bzoj2300$但是效率比较低；
- 考虑直接用线段树，由于标号是顺序更新，所以一段区间的最后一个点被加入后再求区间的凸包，查询线段树查询+三分；
- 实现上凸包的排序可以用归并，（然而并没有快TAT）；
- O(n \ log^2 \ n )

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #include<cmath>

 #include<vector>

 #include<stack>

 #include<map>

 #include<set>

 #define Run(i,l,r) for(int i=l;i<=r;i++)

 #define Don(i,l,r) for(int i=l;i>=r;i--)

 #define ll long long

 #define ld long double

 #define mk make_pair

 #define fir first

 #define sec second

 #define il inline

 #define rg register

 #define pb push_back

 #define ls (k<<1)

 #define rs (k<<1|1)

 using namespace std;

 const int N=;

 const ll inf=1e18;

 int n,cnt,sz[N<<],L[][N<<],R[][N<<];

 ll ans=;

 struct poi{

     ll x,y;

     poi(int _x=,int _y=):x(_x),y(_y){};

     poi operator-(const poi&A)const{return poi(x-A.x,y-A.y);}

     bool operator <(const poi&A)const{return x==A.x?y<A.y:x<A.x;}

 }con[][N],Q,tmp[][N],p[N];

 il char gc(){

     static char*p1,*p2,s[];

     if(p1==p2)p2=(p1=s)+fread(s,,,stdin);

     return(p1==p2)?EOF:*p1++;

 }

 il int rd(){

     int x=,f=; char c=gc();

     while(c<''||c>''){if(c=='-')f=-;c=gc();}

     while(c>=''&&c<='')x=(x<<)+(x<<)+c-'',c=gc();

     return x*f;

 }

 il ll dot(poi A,poi B){return (ll)A.x*B.x+(ll)A.y*B.y;}

 il ll crs(poi A,poi B){return (ll)A.x*B.y-(ll)A.y*B.x;}

 il ll max(ll x,ll y){return x>y?x:y;}

 il void build(int k,int d,int l,int r){

     int mid=(l+r)>>,idl=l,idr=mid+,id=l,top,lst;

     for(;idl<=mid||idr<=r;){

         if(idr>r||(idl<=mid&&tmp[d+][idl]<tmp[d+][idr]))

         tmp[d][id]=tmp[d+][idl],id++,idl++;

         else

         tmp[d][id]=tmp[d+][idr],id++,idr++;

     }

     con[d][L[][k]=top=l]=tmp[d][l];

     for(rg int i=l+;i<=r;++i){

         while(top>l&&crs(con[d][top]-con[d][top-],tmp[d][i]-con[d][top])<=)top--;

         con[d][++top]=tmp[d][i];

     }

     R[][k]=L[][k]=lst=top;

     for(rg int i=r-;i>=l;--i){

         while(top>lst&&crs(con[d][top]-con[d][top-],tmp[d][i]-con[d][top])<=)top--;

         if(i!=l)con[d][++top]=tmp[d][i];

     }

     R[][k]=top;

 }

 il void ask(int k,int d,int typ){

     int l=L[typ][k],r=R[typ][k];

     while(r-l>=){

         int mid=(r-l)/,mid1=l+mid,mid2=r-mid;

         if(dot(con[d][mid1],Q)<dot(con[d][mid2],Q))l=mid1;

         else r=mid2;

     }

     for(rg int i=l;i<=r;++i)ans=max(ans,dot(con[d][i],Q));

     ans=max(ans,dot(con[d][L[][k]],Q));

 }

 il void update(int k,int d,int l,int r,int x){

     if(l==r){

         sz[k]=;

         L[][k]=L[][k]=R[][k]=R[][k]=x;

         tmp[d][x]=con[d][x]=p[x];

     }

     else{

         int mid=(l+r)>>;

         if(x<=mid)update(ls,d+,l,mid,x);

         else update(rs,d+,mid+,r,x);

         sz[k]=sz[ls]+sz[rs];

         if(sz[k]==r-l+)build(k,d,l,r);

     }

 }

 il void query(int k,int d,int l,int r,int x,int y){

     if(l==x&&r==y){ask(k,d,Q.y>);}

     else{

         int mid=(l+r)>>;

         if(y<=mid)query(ls,d+,l,mid,x,y);

         else if(x>mid)query(rs,d+,mid+,r,x,y);

         else query(ls,d+,l,mid,x,mid),query(rs,d+,mid+,r,mid+,y);

     }

 }

 int main(){

     #ifndef ONLINE_JUDGE

     freopen("bzoj3533.in","r",stdin);

     freopen("bzoj3533.out","w",stdout);

     #endif

     char ch,tp;int x,y,l,r;

     n=rd();tp=gc();

     while(!isalpha(tp))tp=gc();

     for(rg int i=;i<=n;++i){

         ch=gc();while(!isalpha(ch))ch=gc();

         if(ch=='A'){

             x=rd();y=rd();

             if(tp!='E')x^=ans,y^=ans;

             p[++cnt]=poi(x,y);

             update(,,,n,cnt);

         }else{

             x=rd();y=rd();l=rd();r=rd();

             if(tp!='E')x^=ans,y^=ans,l^=ans,r^=ans;

             Q=(poi){x,y};

             ans = -inf;

             query(,,,n,l,r);

             printf("%lld\n",ans);

             ans &= 0x7fffffff;

         }

     }

     return ;

 }//by tkys_Austin;

bzoj3533

巴特西

bzoj3533【Sdoi2014】向量集

题目描述

输入格式

输出格式

提示

题解

最新文章

热门文章