考虑到不管怎么变化 \(x_i\) 的值其在 \(t\) 时刻的位置都能被一个一次函数 \(x_i\times t + b\) 表示。
而且 \(b\) 是好算的，考虑到知道现在的斜率 \(k\) 和现在的时间 \(t\) 以及现在的值 \(f(t)\)，则整个函数就是 \(f(x) = f(t) + k\times (x - t)\)，那么 \(b = f(0) = f(t) - k\times t\)。
考虑答案离原点最远。
发现只有两种情况，在原点左边最靠左的点和在原点右边最靠右的点。
其实就是 \(\min\) 和 \(\max\) 取了绝对值后再比一个 \(\max\)。
在加上一次函数，很明显可以用李超线段树来维护。
但是李超线段树不好进行删除操作。
考虑到总共存在的线段只会有 \(O(n + c)\) 条并不多，并且不要求在线，可以离线用线段树分治插入以及撤销。
时间复杂度 \(O((n + c)\log m\log w + q\log w)\)，空间复杂度 \(O((n + c)\log w)\)，\(w\) 是 \(t\) 的值域。
#include<bits/stdc++.h>
using i64 = long long;
const int limw = 1e9, maxQ = 6e5 + 10, maxn = 1e5 + 10, maxp = 2e5;
int n, m;
struct seg {
int k; i64 b;
i64 operator () (const int &x) const {return i64(1) * k * x + b;}
};
struct trmx {
seg mx[maxp]; int ls[maxp], rs[maxp]; int tot, rt;
struct lst {int id; seg mx_; int ls_, rs_;} stk[maxp * 32]; int top;
void init() {
tot = rt = 1;
for (int i = 0; i < maxp; i++) mx[i] = {0, i64(-1e16)};
}
void ins(seg x, int &k, int l, int r) {
! k && (k = ++tot);
stk[++top] = {k, mx[k], ls[k], rs[k]};
int mid = (l + r) >> 1;
x(mid) > mx[k](mid) && (std::swap(x, mx[k]), 1);
x(l) > mx[k](l) && (ins(x, ls[k], l, mid), 1);
x(r) > mx[k](r) && (ins(x, rs[k], mid + 1, r), 1);
}
i64 qry(int x, int k, int l, int r) {
if (! k && l == r) return mx[k](x);
int mid = (l + r) >> 1;
return std::max(mx[k](x), x <= mid ? qry(x, ls[k], l, mid) : qry(x, rs[k], mid + 1, r));
}
void ins(seg x) {ins(x, rt, 0, limw);}
i64 qry(int x) {return qry(x, rt, 0, limw);}
void del(int top_, int tot_) {
tot = tot_;
while (top > top_) {
lst u = stk[top--];
mx[u.id] = u.mx_, ls[u.id] = u.ls_, rs[u.id] = u.rs_;
}
}
} mx;
struct trmn {
seg mn[maxp]; int ls[maxp], rs[maxp]; int tot, rt;
struct lst {int id; seg mn_; int ls_, rs_;} stk[maxp * 32]; int top;
void init() {
tot = rt = 1;
for (int i = 0; i < maxp; i++) mn[i] = {0, i64(1e16)};
}
void ins(seg x, int &k, int l, int r) {
! k && (k = ++tot);
stk[++top] = {k, mn[k], ls[k], rs[k]};
int mid = (l + r) >> 1;
x(mid) < mn[k](mid) && (std::swap(x, mn[k]), 1);
x(l) < mn[k](l) && (ins(x, ls[k], l, mid), 1);
x(r) < mn[k](r) && (ins(x, rs[k], mid + 1, r), 1);
}
i64 qry(int x, int k, int l, int r) {
if (! k && l == r) return mn[k](x);
int mid = (l + r) >> 1;
return std::min(mn[k](x), x <= mid ? qry(x, ls[k], l, mid) : qry(x, rs[k], mid + 1, r));
}
void ins(seg x) {ins(x, rt, 0, limw);}
i64 qry(int x) {return qry(x, rt, 0, limw);}
void del(int top_, int tot_) {
tot = tot_;
while (top > top_) {
lst u = stk[top--];
mn[u.id] = u.mn_, ls[u.id] = u.ls_, rs[u.id] = u.rs_;
}
}
} mn;
seg a[maxn]; int lt[maxn];
std::vector<seg> Q[maxQ * 4];
void upd(int x, int y, seg z, int k = 1, int l = 0, int r = m) {
if (x <= l && r <= y) return Q[k].push_back(z), void();
int mid = (l + r) >> 1;
x <= mid && (upd(x, y, z, k << 1, l, mid), 1), mid < y && (upd(x, y, z, k << 1 | 1, mid + 1, r), 1);
}
int T[maxQ];
void solve(int k = 1, int l = 0, int r = m) {
int topmx = mx.top, topmn = mn.top, totmx = mx.tot, totmn = mn.tot;
for (seg x : Q[k]) mx.ins(x), mn.ins(x);
if (l == r) {
T[l] != -1 && (printf("%lld\n", std::max(std::abs(mx.qry(T[l])), std::abs(mn.qry(T[l])))), 1);
} else {
int mid = (l + r) >> 1;
solve(k << 1, l, mid), solve(k << 1 | 1, mid + 1, r);
}
mx.del(topmx, totmx), mn.del(topmn, totmn);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) a[i].k = 0, scanf("%lld", &a[i].b), lt[i] = 0;
memset(T, -1, sizeof(T));
for (int i = 1; i <= m; i++) {
int t; char s[10]; scanf("%d%s", &t, s);
if (s[0] == 'q') T[i] = t;
else {
int id, k; scanf("%d%d", &id, &k);
upd(lt[id], i - 1, a[id]), lt[id] = i;
i64 now = a[id](t);
a[id] = {k, now - i64(1) * k * t};
}
}
for (int i = 1; i <= n; i++) upd(lt[i], m, a[i]);
solve();
return 0;
}