线段树优化凸壳

Lena and Queries

题目链接：http://codeforces.com/contest/678/problem/F

三种操作，1.插入一个点$(x,y)$ 2.删除之前第$i$个操作插入的点 3.给一个$q$，询问在已有点中$qx+y$最大是多少

如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立，所以不能cdq分治。

但是可以用上一次线段树优化建图一样的技巧，按时间来看，因为每个点的存在是一段区间，那么就可以用线段树拆成log个区间，然后把点“打”在上面（加进vector），最后对于线段树上每个区间，做凸壳然后询问就行了。每个询问会被问log次，所以时间复杂度粗略算有$O(nlog^2n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
const ll NINF=1LL<<63;
struct Point
{
    ll x,y;
    Point(){}
    Point(ll x_,ll y_)
    {
        x=x_;
        y=y_;
    }
    Point operator -(const Point &t)const
    {
        return Point(x-t.x,y-t.y);
    }
    ll operator *(const Point &t)const
    {
        return x*t.x+y*t.y;
    }
    ll operator ^(const Point &t)const
    {
        return x*t.y-t.x*y;
    }
    bool operator <(const Point &t)const
    {
        return x<t.x||(x==t.x && y<t.y);
    }
} p[N],res[N];
vector<Point> v[N<<2];
int opt[N];
bool del[N],emp[N];
int n,top;
ll ans[N];
void insert(int o,int l,int r,int ql,int qr,int x)
{
    if(ql<=l && r<=qr)
    {
        v[o].push_back(p[x]);
        return;
    }
    int mid=l+r>>1;
    if(ql<=mid) insert(o<<1,l,mid,ql,qr,x);
    if(mid<qr) insert(o<<1|1,mid+1,r,ql,qr,x);
}
void ask(int o)
{
    int l=1,r=top;
    while(r-l>=3)
    {
        int x=(l*2+r)/3;
        int y=(l+2*r)/3;
        if(p[o]*res[x]<p[o]*res[y]) l=x;
        else r=y;
    }
    for(int i=l;i<=r;++i)
        ans[o]=max(ans[o],p[o]*res[i]);
}
void solve(int o,int l,int r)
{
    if(l<r)
    {
        int mid=l+r>>1;
        solve(o<<1,l,mid);
        solve(o<<1|1,mid+1,r);
    }
    sort(v[o].begin(),v[o].end());
    top=0;
    //cout<<o<<" "<<l<<" "<<r<<" "<<v[o].size()<<endl;
    for(int i=0;i<v[o].size();++i)
    {
        while(top>1 && ((res[top]-res[top-1])^(v[o][i]-res[top]))>=0) --top;
        res[++top]=v[o][i];
    }
    for(int i=l;i<=r;++i)
        if(opt[i]==3 && !emp[i])
        {
            //cout<<"ask"<<endl;
            ask(i);
            //cout<<ans[i]<<endl;
        }
}
int main()
{
    scanf("%d",&n);
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&opt[i]);
        if(opt[i]==1)
        {
            scanf("%lld%lld",&p[i].x,&p[i].y);
            ++cnt;
        }
        else if(opt[i]==2)
        {
            int x;
            scanf("%d",&x);
            del[x]=true;
            --cnt;
            insert(1,1,n,x,i-1,x);
        }
        else
        {
            scanf("%lld",&p[i].x);
            p[i].y=1;
            if(cnt==0) emp[i]=true;
        }
    }
    for(int i=1;i<=n;++i)
        if(opt[i]==1 && !del[i])
            insert(1,1,n,i,n,i);
    for(int i=1;i<=n;++i) ans[i]=NINF;

    solve(1,1,n);
    for(int i=1;i<=n;++i)
    if(opt[i]==3)
    {
        if(emp[i]) printf("EMPTY SET\n");
        else printf("%lld\n",ans[i]);
    }
    return 0;
}
/*
3
1 -1 0
1 -1 1
3 -2
*/