Description

你要維護一個向量集合，支持以下操作：
1.插入一個向量 \((x,y)\)
2.刪除插入的第 \(i\) 個向量
3.查詢當前集合與 \((x,y)\) 點積的最大值是多少。如果當前是空集輸出 \(0\)

Input

第一行輸入一個整數(shù) \(n\) ，表示操作個數(shù)
接下來 \(n\) 行，每行先是一個整數(shù) \(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 \leq 200000\) \(1 \leq x,y \leq 10^6\)

想法

每個向量只對一定范圍內(nèi)的查詢操作可能有貢獻，于是可以線段樹分治。

具體就是將詢問按時間編號為 \(1~m\) ，建一棵線段樹。
每個向量 \(insert\) 到它有貢獻的區(qū)間中，注意找到完全包含在它的貢獻區(qū)間的節(jié)點后打上標記就行了，不需要下放！
怎么打標記呢？就是對每個節(jié)點開一個 \(vector\) ，把向量扔進去就行了。

接著我們考慮，“求集合中與\((x,y)\) 點積的最大值” 怎么搞。
對于集合中的兩個向量，\((u1,v1) 和 (u2,v2)\) ，不妨設(shè) \(u1<u2\)
若前者不如后者，即 \((u1,v1) \cdot (x,y) < (u2,v2) \cdot (x,y)\)
打開并整理一下得出 \(-\frac{x}{y} < \frac{v2-v1}{u2-u1}\)
也就是說我們需要維護斜率遞減的凸包。

為了維護方便，我們將向量們按 \(x\) 坐標從小到大依次 \(insert\) 到線段樹中，線段樹的每個節(jié)點維護一個凸包。
最終查詢的時候，在線段樹上從根到特定葉子的路徑上每個節(jié)點維護的凸包中二分最優(yōu)解，更新答案。
每次查詢復(fù)雜度 \(O(log^2n)\) ， 總復(fù)雜度 \(O(nlog^2n)\)

代碼

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int read(){
    int x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10 ch-'0',ch=getchar();
    return x;
}
 
const int N = 200005;
typedef long long ll;
 
int tot,n,m;
struct data{ int x,y,l,r; }d[N],q[N];
bool cmp(data x,data y) { return x.x<y.x; }
 
int root,cnt;
int ch[N*2][2];
vector<data> v[N*2];
void build(int x,int l,int r){
    if(l==r) return;
    int mid=(l r)>>1;
    build(ch[x][0]=  cnt,l,mid);
    build(ch[x][1]=  cnt,mid 1,r);
}
bool bigk(data a,data b,data c) { return 1ll*(b.y-a.y)*(c.x-b.x)<=1ll*(c.y-b.y)*(b.x-a.x); }
void ins(int x,int l,int r,int L,int R,int c){
    if(l==L && r==R){ 
        while(v[x].size()>1 && bigk(v[x][v[x].size()-2],v[x][v[x].size()-1],d[c])) v[x].pop_back();
        v[x].push_back(d[c]);
        return;
    }
    int mid=(l r)>>1;
    if(R<=mid) ins(ch[x][0],l,mid,L,R,c);
    else if(L>mid) ins(ch[x][1],mid 1,r,L,R,c);
    else{
        ins(ch[x][0],l,mid,L,mid,c);
        ins(ch[x][1],mid 1,r,mid 1,R,c);
    }
}
bool check(data a,data b,data c) { return 1ll*c.y*(a.y-b.y)<1ll*c.x*(b.x-a.x); }
ll ask(int x,int l,int r,int c){
    ll ret=0;
    if(v[x].size()>=1){
        int L=0,R=v[x].size()-1,mid;
        while(L<R){
            mid=(L R)>>1;
            if(check(v[x][mid],v[x][mid 1],q[c])) L=mid 1;
            else R=mid;
        }
        ret=1ll*q[c].x*v[x][L].x 1ll*q[c].y*v[x][L].y;
    }
     
    if(l==r) return ret;
    int mid=(l r)>>1;
    if(c<=mid) return max(ret,ask(ch[x][0],l,mid,c));
    return max(ret,ask(ch[x][1],mid 1,r,c));
}
 
int main()
{
    int Q,t,id,x,y;
    Q=read();
    while(Q--){
        t=read();
        if(t==1) {
            x=read(); y=read();
            d[  m]=(data){x,y,n 1,-1};
        }
        else if(t==2){
            id=read();
            d[id].r=n;
        }
        else {
            x=read(); y=read();
            q[  n]=(data){x,y,0,0};
        }
    }
    for(int i=1;i<=m;i  ) if(d[i].r==-1) d[i].r=n;
    sort(d 1,d 1 m,cmp);
     
    build(root=  cnt,1,n);
    for(int i=1;i<=m;i  )
        if(d[i].l<=d[i].r) ins(root,1,n,d[i].l,d[i].r,i);
     
    for(int i=1;i<=n;i  ) printf("%lld\n",ask(root,1,n,i));
     
    return 0;
} 
?