[BZOJ4311]向量

题目

Description

你要维护一个向量集合，支持以下操作： 1.插入一个向量(x,y) 2.删除插入的第i个向量 3.查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0

Input

第一行输入一个整数n，表示操作个数接下来n行，每行先是一个整数t表示类型，如果t=1，输入向量 (x,y)；如果t=2，输入id表示删除第id个向量；否则输入(x,y)，查询与向量(x,y)点积最大值是多少。保证一个向量只会被删除一次，不会删没有插入过的向量

Output

对于每条t=3的询问，输出一个答案

Sample Input

Sample Output

18
15

HINT

n<=200000 1<=x,y<=10^6

题解

每个向量出现的时间是一段区间，所以可以用线段树分治搞

$(x_1,y_1),(x_2,y_2)$点积是$x_1x_2+y_1y_2$

如果对$(x_1,y_1),(x_2,y_2)$查询向量$(x,y)$，假设$(x_1,y_1)$点积更大，则有式子$xx_1+yy_1>xx_2+yy_2$

即$x(x_1-x_2)>y(y_2-y_1)$

即$-\frac{x}{y}>\frac{y_1-y_2}{x_1-x_2}$

右边的是个斜率，左边的是直线$y=kx$的垂线

所以维护斜率凸壳即可

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=2e5+5;
struct p{
    int x,y,l,r;
    bool operator< (const p &a)
    const{
        if(x!=a.x) return x<a.x;
        return y<a.y;
    }
}qu[MAX];
struct q{
    int x,y;
}qwq[MAX],st[MAX];
int n,cnt,T,top;
int L[MAX];
LL ans[MAX];
vector<int> s[MAX<<2];
int read()
{
    int x(0);
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
    return x;
}
void change(int l,int r,int k,int L,int R,int id)
{
    if(L>R) return;
    if(l==L&&r==R) return void(s[k].push_back(id));
    if(R<=mid) change(l,mid,tl,L,R,id);
    else if(L>mid) change(mid+1,r,tr,L,R,id);
    else change(l,mid,tl,L,mid,id),change(mid+1,r,tr,mid+1,R,id);
}
LL GET_NUM(q a,q b)
{
    return 1ll*a.x*b.x+1ll*a.y*b.y;
}
LL calc(q a,q b,q c)
{
    return 1ll*(a.x-c.x)*(b.y-c.y)-1ll*(a.y-c.y)*(b.x-c.x);
}
LL GET_ANS(int x)
{
    int l=1,r=top;
    while(l+3<=r)
    {
        int mid1=(l+r>>1),mid2=(mid1+r>>1);
        if(GET_NUM(qwq[x],st[mid1])<=GET_NUM(qwq[x],st[mid2])) l=mid1;
        else r=mid2;
    }
    LL ans=0;
    for(int i=l;i<=r;++i)
      ans=max(ans,GET_NUM(qwq[x],st[i]));
    return ans;
}
void Solve(int l=1,int r=n,int k=1)
{
    top=0;
    for(int i=0,cnt=s[k].size();i<cnt;++i)
      {
        p tt=qu[s[k][i]];
        while(top>1&&calc(st[top-1],st[top],(q){tt.x,tt.y})>=0) --top;
        st[++top]=(q){tt.x,tt.y};
      }
    if(s[k].size()) for(int i=l;i<=r;++i)
      if(qwq[i].x) ans[i]=max(ans[i],GET_ANS(i));
    if(l==r) return;
    Solve(l,mid,tl),Solve(mid+1,r,tr);
}
int main()
{
    n=read();
    memset(ans,-1,sizeof(ans));
	for(int i=1,op,x,y;i<=n;++i)
      {
        op=read(),x=read();
        if(op==1) qu[++cnt]=(p){x,read()},L[cnt]=i;
        else if(op==2) qu[x].l=L[x],qu[x].r=i-1,L[x]=0;
        else if(op==3) qwq[i]=(q){x,read()},ans[i]=0;
      }
    for(int i=1;i<=cnt;++i)
      if(L[i]) qu[i].l=L[i],qu[i].r=n;
    sort(qu+1,qu+1+cnt);
    for(int i=1;i<=cnt;++i)
      change(1,n,1,qu[i].l,qu[i].r,i);
    Solve();
    for(int i=1;i<=n;++i)
      if(ans[i]!=-1) printf("%lld\n",ans[i]);
    return 0;
}

题目