描述

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

5

1 3 3

1 1 4

3 3 3

2 1

3 3 3

Sample Output

18

15

HINT

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

Source

NOI2015模拟题by 杨定澄

分析

所有向量都在第一象限，根据点积的定义，我们作询问向量OQ的垂线，从无穷远处向原点扫描过来，碰到的集合中的第一个点对应的向量和OQ的点积一定是最大的。

可以发现，这样的点一定在原集合点集的上凸包上，我们只要建出凸包，在凸包上二分（或三分）就可以找到那个点。。

如果没有删除操作，我们可以用CDQ分治来做这道题。

但是有了删除操作，一个向量只能在一段询问区间内生效，我们可以用线段树分治来做。

我们对询问建立线段树，然后把每一个向量插入到对应的询问区间，然后对每个节点建立凸包。

每次询问，对对应节点到根路径上的所有节点都进行一次查询即可得到答案。时间复杂度O(nlog2n)

我们可以将向量排序后插入，在求凸包的时候就不用再排序了。把所有询问按照极角排序后，发现决策点单调，那极角排序后再将询问插入线段树即可。我们遍历一遍线段树，同时进行归并排序，然后处理这个节点的向量对这个节点包含的询问的贡献，可以节省一些空间。时间复杂度O(nlogn)

代码 ==

#include
     
      #include
      
       #include
       
        #define MAXN 200000using namespace std;void Read(int &x){    static char c;    while(c=getchar(),c!=EOF)        if(c>='0'&&c<='9'){            x=c-'0';            while(c=getchar(),c>='0'&&c<='9')                x=x*10+c-'0';            ungetc(c,stdin);            return;        }}int n,ocnt,qcnt,bk,tmp[MAXN+10],tmp2[MAXN+10];long long ans[MAXN+10];struct point{    int x,y;    inline point(){    }    inline point(int x,int y):x(x),y(y){    }    inline point operator-(const point &b)const{        return point(x-b.x,y-b.y);    }    bool operator<(const point &b)const{        if(x==b.x)            return y
        
         op;}tree[MAXN*4+10];void insert(int i,int l,int r,int ll,int rr,point *a){    if(ll<=l&&r<=rr){        tree[i].op.push_back(a);        return;    }    if(ll>r||rr
         
          >1);    insert(i<<1,l,mid,ll,rr,a);    insert((i<<1)|1,mid+1,r,ll,rr,a);}void read(){    Read(n);    int i,p,x,y;    for(i=1;i<=n;i++){        Read(p),Read(x);        if(p==1){            Read(y);            cg[++ocnt].x=point(x,y);            cg[ocnt].l=qcnt+1;            cg[ocnt].r=-1;        }        else if(p==2)            cg[x].r=qcnt;        else{            Read(y);            Q[++qcnt]=point(x,y);        }    }    sort(cg+1,cg+ocnt+1);    for(i=1;i<=ocnt;i++){        if(cg[i].r==-1)            cg[i].r=qcnt;        if(cg[i].l>cg[i].r)            continue;        insert(1,1,qcnt,cg[i].l,cg[i].r,&cg[i].x);    }}void Divide_Conqure(int i,int l,int r){    if(l==r){        tmp[l]=l;        for(vector
          
           ::iterator j=tree[i].op.begin();j
           
            >1),x,j,k; Divide_Conqure(i<<1,l,mid); Divide_Conqure((i<<1)|1,mid+1,r); x=l,j=mid+1,k=l; while(x<=mid||j<=r){ if(j>r||(x<=mid&&cross(Q[tmp[x]],Q[tmp[j]])<=0)) tmp2[k++]=tmp[x++]; else tmp2[k++]=tmp[j++]; } bk=0; for(x=l;x<=r;x++) tmp[x]=tmp2[x]; for(vector
            
             ::iterator v=tree[i].op.begin();v
             
              1&&cross(*q[bk]-*q[bk-1],**v-*q[bk-1])>=0) bk--; q[++bk]=*v; } if(bk){ for(x=l,j=1;x<=r;x++){ while(j
              
               dot(Q[tmp[x]],*q[j])) j++; ans[tmp[x]]=max(ans[tmp[x]],dot(Q[tmp[x]],*q[j])); } }}void print(){ int i; for(i=1;i<=qcnt;i++) printf("%lld\n",ans[i]);}int main(){ read(); Divide_Conqure(1,1,qcnt); print();}