实际上并不是 DP（
然而斜率优化的都算在这个标签里吧（
考虑静态的问题，即不需要动态插入的问题。
对于一个询问 \((X,Y)\)，考虑两个决策 \(i,j\)，不妨设 \(y_i \ge y_j\)。
设 \(i\) 比 \(j\) 优，则 \[
\begin{aligned}
X \cdot x_i + Y \cdot y_i & > X \cdot x_j + Y \cdot y_j \\
X(x_i - x_j) & > -Y(y_i - y_j) \\
\frac{x_i - x_j}{y_i - y_j} & > -\frac YX
\end{aligned}
\]
注意到这是一个斜率的形式，考虑排序后使用单调队列维护上凸包实现斜率优化便可回答询问。
考虑插入和删除。
注意到这是线段树分治的基本操作，套上一层线段树分治即可。
复杂度共 \(O(n \log n)\)（在一开始排好序）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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]);
}