JZOJ 4179 向量

实际上并不是 DP（
然而斜率优化的都算在这个标签里吧（

考虑静态的问题，即不需要动态插入的问题。
对于一个询问 (X,Y)，考虑两个决策 i,j，不妨设 yi≥yj。
设 i 比 j 优，则 X⋅xi+Y⋅yi>X⋅xj+Y⋅yjX(xi−xj)>−Y(yi−yj)xi−xjyi−yj>−YX

注意到这是一个斜率的形式，考虑排序后使用单调队列维护上凸包实现斜率优化便可回答询问。

考虑插入和删除。
注意到这是线段树分治的基本操作，套上一层线段树分治即可。
复杂度共 O(nlogn)（在一开始排好序）。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 2e5;
int n;
struct s_change
{
    int x,y,l,r;
    inline bool operator<(const s_change &o) const
    {
        return y < o.y || (y == o.y && x > o.x);
    }
} chg[N + 5];
int chg_tot;
vector<int> seg[(N << 4) + 10];
struct s_query
{
    int t,id,x,y;
    inline bool operator<(const s_query &o) const
    {
        return (long long)y * o.x < (long long)o.y * x;
    }
} qry[N + 5];
long long ans[N + 5];
int qry_tot;
void update(int l,int r,int x,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        seg[p].push_back(x);
        return ;
    }
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,x,ls,tl,mid),1);
    r > mid && (update(l,r,x,rs,mid + 1,tr),1);
}
inline double slope(int x,int y)
{
    if(chg[x].y == chg[y].y)
        return -1e18;
    return (double)(chg[x].x - chg[y].x) / (chg[x].y - chg[y].y);
}
void solve(int l,int r,int p,int tl,int tr)
{
    if(l > r)
        return ;
    static int q[N + 5],head,tail;
    head = 1,tail = 0;
    for(register vector<int>::iterator it = seg[p].begin();it != seg[p].end();++it)
    {
        for(;head < tail && slope(q[tail - 1],q[tail]) < slope(q[tail],*it);--tail);
        q[++tail] = *it;
    }
    for(register int i = l;i <= r;++i)
    {
        for(;head < tail && slope(q[head],q[head + 1]) > -(double)qry[i].y / qry[i].x;++head);
        head <= tail && (ans[qry[i].id] = max(ans[qry[i].id],(long long)chg[q[head]].x * qry[i].x + (long long)chg[q[head]].y * qry[i].y));
    }
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    static s_query buf[2][N + 5];
    int tot[2] = {0};
    for(register int i = l;i <= r;++i)
        buf[qry[i].t > mid][++tot[qry[i].t > mid]] = qry[i];
    for(register int i = 1;i <= tot[0];++i)
        qry[l + i - 1] = buf[0][i];
    for(register int i = 1;i <= tot[1];++i)
        qry[l + tot[0] + i - 1] = buf[1][i];
    solve(l,l + tot[0] - 1,ls,tl,mid),solve(l + tot[0],r,rs,mid + 1,tr);
}
int main()
{
    scanf("%d",&n);
    int op,x,y;
    for(register int i = 1;i <= n;++i)
    {
        scanf("%d%d",&op,&x);
        if(op == 1)
            scanf("%d",&y),chg[++chg_tot] = {x,y,i,0};
        else if(op == 2)
            chg[x].r = i;
        else
            scanf("%d",&y),qry[++qry_tot] = {i,qry_tot,x,y};
    }
    sort(chg + 1,chg + chg_tot + 1),sort(qry + 1,qry + qry_tot + 1);
    for(register int i = 1;i <= chg_tot;++i)
        !chg[i].r && (chg[i].r = n),update(chg[i].l,chg[i].r,i,1,1,n);
    solve(1,qry_tot,1,1,n);
    for(register int i = 1;i <= qry_tot;++i)
        printf("%lld\n",ans[i]);
}