statement
给定 \(n\) 个人，每个人从 \(T_i\) 秒开始从 \(a_i\) 移动到 \(b_i\)，每秒移动一个单位。给定 \(q\) 个保镖，每个保镖从 \(P_i\) 秒开始，从 \(x_i\) 开始移动，每秒一个单位。如果保镖和人在同一个位置上，就可以获得 \(C_i\) 的奖金，问每个保镖最多能获得多少奖金。
analysis
考虑到人不多，先对所有人的位置进行离散化。我们可以尝试用 \((\text{时间},\text{坐标})\) 的二维平面刻画每一个人。那么对于任意一个人的行动轨迹应该是一条与 \(y=x\) 或 \(y=-x\) 平行的直线。而保镖的图像也是由若干这样的直线拼接而成的。
注意到所有直线之间的夹角均为 \(90^\circ\)，我们可以将所有直线顺时针翻转 \(45^\circ\)，使其与坐标轴平行。
平面直角坐标系中，将 \((x,y)\) 翻转 \(\theta\) 度（逆时针）的坐标可以由如下矩阵得到：
\(\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta \end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix}\)
可以从向量的角度证明此结论。
则 \((x,y)\) 翻转 \(45^\circ\) 得到的是 \((\frac{\sqrt 2}{2}x-\frac{\sqrt 2}{2}y,\frac{\sqrt 2}{2}x + \frac{\sqrt 2}{2}y)\)
由于 \(\sqrt 2\) 在计算机中并不好处理，我们将所有的线段长度都扩大至 \(\sqrt 2\) 倍，那么得到的坐标就是 \((x-y,x+y)\)。
那么现在在新矩形中一条边的长度是走过路径长的两倍（在原来的二维平面中由直边转为斜边，这里又翻了 \(\sqrt 2\) 倍）。
现在每个人可以用一条竖着的线段或横着的线段表示。
考虑保镖只能向上和向右走，那么 dp 可以解决，然而保镖的数量非常大，要换一种考虑方式。
设 \(f_{i,j}\) 表示从 \((i,j)\) 开始向上和向右走可以获得的最大收益，保镖可以分为这样两段路：
- 从自身的起点开始走到自己右上方的一个已经求出 \(f\) 的起点
- 从 \((i,j)\) 走出去
可以预处理出 \(f_{i,j}\)，时间复杂度 \(\mathcal O(n^2)\)。
那么问题转化为如何求一个点右上方最优的点。
对于任意一个起点，我们第一段路只有两种可能，要么先向上再向右，要么先向右再向上。可以发现，答案和点到最优解之间的横/纵距离呈线性关系。
如图，\((i,j)\) 是 \((x,y)\) 这个点的最优解，则答案和 \(i-x\) 或 \(j-y\) 是有线性关系的。
那么我们可据此将每个点转换成直线，\(y_t=c_ix+f_{i,j}\)，在李超树上求解最大值即可。
代码中我还没完全搞明白旋转之后的坐标关系，所以横纵坐标实际上是反过来的，其实这无关紧要，可以看作是关于 \(y=x\) 这根直线翻折得到，路径并没有受到改变，mxU 和 mxR 统计的是路径上 \(c\) 的最大值。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 6005, M = 3e6 + 5;
ll xl[N], xr[N], yl[N], yr[N], c[N], lshx[N], lshy[N];
int n, q, qx[M], qy[M];
ll ans[M], dp[N][N], mxR[N][N], mxU[N][N];
vector<int> inX[N], inY[N];
inline ll read() {
ll x = 0;
int f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c & 15);
return f ? -x : x;
}
namespace sgt {
const int L = 15005;
int tot, tag[L], lc[L], rc[L];
ll K[L], B[L];
int ln;
inline void add(ll k, ll b) { ++ln, K[ln] = k, B[ln] = b; }
inline ll y(int id, ll x) { return K[id] * x + B[id]; }
void Change(int& k, ll l, ll r, int id) {
if (!k) k = ++tot;
if (l == r) {
if (!tag[k] || y(tag[k], l) < y(id, l)) tag[k] = id;
return;
}
if (!tag[k]) return tag[k] = id, void();
ll mid = l + r >> 1;
ll y1 = y(tag[k], mid), y2 = y(id, mid);
if (K[tag[k]] > K[id]) {
if (y1 >= y2)
Change(lc[k], l, mid, id);
else {
Change(rc[k], mid + 1, r, tag[k]);
tag[k] = id;
}
} else if (K[tag[k]] < K[id]) {
if (y1 >= y2)
Change(rc[k], mid + 1, r, id);
else {
Change(lc[k], l, mid, tag[k]);
tag[k] = id;
}
} else if (B[tag[k]] < B[id])
tag[k] = id;
}
ll Query(int k, ll l, ll r, ll x) {
if (!k) return -LONG_LONG_MAX;
ll res = y(tag[k], x);
ll mid = l + r >> 1;
if (l == r) return res;
if (x <= mid)
return max(res, Query(lc[k], l, mid, x));
else
return max(res, Query(rc[k], mid + 1, r, x));
}
} // namespace sgt
using namespace sgt;
// inline void chkmax(int& x, const int y) { x = x < y ? y : x; }
inline void chkmax(ll& x, const ll y) { x = x < y ? y : x; }
int main() {
n = read(), q = read();
for (int i = 1; i <= n; ++i) {
ll t = read(), a = read(), b = read();
c[i] = read() / 2;
// before: x = t, y = a; x = t + abs(b - a), y = b;
xl[i] = t + a;
yl[i] = t - a;
xr[i] = t + abs(b - a) + b;
yr[i] = t + abs(b - a) - b;
lshx[i * 2 - 1] = xl[i];
lshx[i * 2] = xr[i];
lshy[i * 2 - 1] = yl[i];
lshy[i * 2] = yr[i];
}
sort(lshx + 1, lshx + n * 2 + 1);
sort(lshy + 1, lshy + n * 2 + 1);
int cntx = unique(lshx + 1, lshx + n * 2 + 1) - lshx - 1;
int cnty = unique(lshy + 1, lshy + n * 2 + 1) - lshy - 1;
for (int i = 1; i <= n; ++i) {
xl[i] = lower_bound(lshx + 1, lshx + cntx + 1, xl[i]) - lshx;
xr[i] = lower_bound(lshx + 1, lshx + cntx + 1, xr[i]) - lshx;
yl[i] = lower_bound(lshy + 1, lshy + cnty + 1, yl[i]) - lshy;
yr[i] = lower_bound(lshy + 1, lshy + cnty + 1, yr[i]) - lshy;
}
for (int i = 1; i <= n; ++i) {
if (xl[i] == xr[i])
for (int j = min(yl[i], yr[i]); j < max(yl[i], yr[i]); ++j)
chkmax(mxU[xl[i]][j], c[i]);
else // yl[i] == yr[i]
for (int j = min(xl[i], xr[i]); j < max(xl[i], xr[i]); ++j)
chkmax(mxR[j][yl[i]], c[i]);
}
for (int i = cntx; i >= 1; --i) {
for (int j = cnty; j >= 1; --j) {
chkmax(dp[i][j], dp[i + 1][j] + 1ll * mxR[i][j] * (lshx[i + 1] - lshx[i]));
chkmax(dp[i][j], dp[i][j + 1] + 1ll * mxU[i][j] * (lshy[j + 1] - lshy[j]));
}
}
for (int i = 1; i <= q; ++i) {
int p = read(), x = read();
qx[i] = p + x, qy[i] = p - x;
inX[lower_bound(lshx + 1, lshx + cntx + 1, qx[i]) - lshx].emplace_back(i);
}
for (int i = 1; i <= cntx; ++i) {
for (int j = 1; j <= cnty; ++j) inY[j].clear();
for (int j : inX[i])
inY[lower_bound(lshy + 1, lshy + cnty + 1, qy[j]) - lshy].emplace_back(j);
memset(lc, 0, sizeof(lc));
memset(rc, 0, sizeof(rc));
memset(tag, 0, sizeof(tag));
tot = ln = 0;
for (int j = cnty; j >= 1; --j) {
add(mxR[i - 1][j], dp[i][j]);
Change(lc[0], 0, 4e9, ln);
for (int v : inY[j]) chkmax(ans[v], Query(1, 0, 4e9, lshx[i] - qx[v]));
}
}
for (int i = 1; i <= cnty; ++i) inY[i].clear();
for (int i = 1; i <= q; ++i)
inY[lower_bound(lshy + 1, lshy + cnty + 1, qy[i]) - lshy].emplace_back(i);
for (int i = 1; i <= cnty; ++i) {
for (int j = 1; j <= cntx; ++j) inX[j].clear();
for (int j : inY[i])
inX[lower_bound(lshx + 1, lshx + cntx + 1, qx[j]) - lshx].emplace_back(j);
memset(lc, 0, sizeof(lc));
memset(rc, 0, sizeof(rc));
memset(tag, 0, sizeof(tag));
tot = ln = 0;
for (int j = cntx; j >= 1; --j) {
add(mxU[j][i - 1], dp[j][i]);
Change(lc[0], 0, 4e9, ln);
for (int v : inX[j]) chkmax(ans[v], Query(1, 0, 4e9, lshy[i] - qy[v]));
}
}
for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
return 0;
}
此题还有一种更精妙的 \(\mathcal O(nq)\) 做法，感兴趣的读者可以自行研究。Hint：用单调栈代替李超树。
标签：保镖,int,ll,Day3,JOISC,tag,2021,id,dp From： https://www.cnblogs.com/misterrabbit/p/17450430.html