闲话
武汉一程又诞生了许多梗（
比方说 常求暴政cgy 和 午饭点哪家外卖
昨天没写闲话是因为返校了懒得写！
打了几个新买的游戏 发现没通关就没兴趣了（
这就是我的末路吗（
当然大概是游戏力太低了
今日推歌：WonderRuins - 晴いちばん feat. 初音ミク
作者写这首歌的时候才 15 岁（
你们霓虹人不会调 v 曲犯法吗？（
挺好听的！
模拟赛
T1
题目是背包板子，那我们就用背包板子做这题。设 \(a_i\) 的值域是 \(V\)。
考虑二进制分组，我们将每个 \(a_i\) 拆分成 \(2^0, 2^1, \dots, 2^k, s\) 的形式，随后将 \(s\) 接着拆分，直到拆分使得 \(s = 0\)。这样一个物品会被最多拆出 \(\log^2 V\) 个物品，并且这些物品都形如 \(b_i\times 2^k\) 的形式。对每个 \(k\) 保存这样的所有物品。
接下来就是对一系列 \(b_i\times 2^k\) 重量的物品做 01 背包了，考虑数位 dp。我们从低位到高位确定答案，设当前确定到了第 \(k\) 位。
首先考虑进位。从下面往上进的重量是 \(b\times 2^{k - 1}\)。随后我们可以考虑向 \(k\) 转移，第 \(k\) 位的值是 \(b \& 1\)，进上去的重量是 \(\left\lfloor\frac{b}{2}\right\rfloor\)。但这样不是很方便统计答案，我们最后只能确定第 \(\log_2 m\) 位的 \(01\) 性，无法确定下面是否超过 \(m\) 的低 \(\log_2 m - 1\) 位。这样我们不妨记录一个布尔值，表示低 \(k\) 位是否会超过 \(m\)，这可以在过程中按填入第 \(k\) 位的值和当前 \(m\) 第 \(k\) 位的值维护转移方向。设目前的状态是 \(f(k, b, 0/1)\)。
随后考虑向背包中加物品，这也可以按普通 01 背包的方式对第二位做背包。
这样做的总时间复杂度是 \(O(C\log^2 V\log m)\) 的；第二维大小不太会分析，但可以卡到 \(C = 42500\)。
考虑优化常数(?)。我们不需要接着将 \(s\) 拆分为低 \(k\) 位的所有值，我们只需要将 \(s\) 二进制分解为 \(\sum 2^{k_i}\) 的形式即可，这样总是合法的。因此优化到 \(\log^2 V\to \log V\)，$C \approx 1500 $。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 65;
int n, b[N], cnt[N];
ll a[N], c[N], m;
lll ans, f[N][2005][2];
vector<pair<int, lll> > g[N];
signed main() {
cin >> n;
rep(i,1,n) {
cin >> a[i] >> b[i] >> c[i];
ll tmp = a[i];
for (int k = 0; tmp >= (1ll << k); ++ k) {
tmp -= (1ll << k);
g[k].eb(b[i], (lll)c[i] * (1ll << k)), cnt[k] += b[i];
} while (tmp > 0) {
int k = __lg(tmp & -tmp);
g[k].eb(b[i], (lll)c[i] * (1ll << k)), cnt[k] += b[i];
tmp ^= tmp & -tmp;
}
} cin >> m;
rep(k,0,__lg(m)) {
if (k) {
pre(i,cnt[k-1],0) {
if ((m >> (k - 1) & 1) < (i & 1)) f[k][i / 2][1] = max( { f[k][i / 2][1], f[k - 1][i][1], f[k - 1][i][0] } );
else f[k][i / 2][0] = max(f[k][i / 2][0], f[k - 1][i][0]), f[k][i / 2][1] = max(f[k][i / 2][1], f[k - 1][i][1]);
} cnt[k] += cnt[k - 1] / 2;
} cerr << cnt[k] << '\n';
for (auto [w, v] : g[k]) pre(i,cnt[k],w)
f[k][i][0] = max(f[k][i][0], f[k][i - w][0] + v), f[k][i][1] = max(f[k][i][1], f[k][i - w][1] + v);
}
ans = max( { f[__lg(m)][0][1], f[__lg(m)][0][0], f[__lg(m)][1][0] } );
cout << ans << '\n';
}
T2
\(O(n^3)\) 的做法比较好想。设 \(f(i, j)\) 是从 \(i\) 出发，检查节点 \(i\) 到 节点 \(j\) 之间的最小代价，这里 \(i < j\) 不恒成立。设 \(p = \min(i, j), q = \max(i, j)\)，显然有
初值是 \(\lvert i -j\rvert = 1\) 时 \(f(i, j) = 0\)。
考虑设 \(f(0, i, j)\) 为 \(i < j\) 的情况，\(f(1, i, j)\) 为 \(i > j\) 的情况。
显然 \(f(0), f(1)\) 分别是单调的，所以存在位置 \(p\) 使得 \(k\le p\) 时 \(\min\) 取前者，\(k>p\) 时 \(\min\) 取后者。\(p\) 也是随 \(i,j\) 单调的，所以用双指针维护 \(p\) 然后一边直接维护最大值，另一边用单调栈维护凸包和决策点即可。\(g_{i,j}\) 的求解方法同理。
注意到维护凸包时，我们的切线斜率变化单调，且是向着凸包起始位置倾斜，这导致我们的决策点会向两个方向移动，不过移动步数总和仍然是 \(O(n)\) 的。
总时间复杂度 \(O(n^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 3000 + 5;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, s[N], p[N];
ll d[N], f[N][N][2];
ll mxl, mxr[N];
struct Chull {
int stk[N], top;
ll yv[N];
inline void addl(int x, ll y) {
yv[x] = y;
while (top > 1 and 1ll * (s[stk[top]] - s[stk[top - 1]]) * (yv[x] - yv[stk[top]]) <= 1ll * (s[x] - s[stk[top]]) * (yv[stk[top]] - yv[stk[top - 1]])) -- top;
stk[++ top] = x;
}
inline void addr(int x, ll y) {
yv[x] = y;
while (top > 1 and 1ll * (s[stk[top]] - s[stk[top - 1]]) * (yv[x] - yv[stk[top]]) >= 1ll * (s[x] - s[stk[top]]) * (yv[stk[top]] - yv[stk[top - 1]])) -- top;
stk[++ top] = x;
}
ll query(int k) {
if (!top) return -1e16;
while (top > 1 and yv[stk[top]] - 1ll * k * s[stk[top]] < yv[stk[top - 1]] - 1ll * k * s[stk[top - 1]]) -- top;
return yv[stk[top]] - 1ll * k * s[stk[top]];
}
} lhull, rhull[N];
signed main() {
cin >> n;
rep(i,1,n) cin >> s[i]; s[0] = 0, s[n + 1] = 114514;
rep(i,1,n) cin >> d[i]; p[n + 1] = n + 1;
pre(i,n,0) {
p[i] = i, mxl = lhull.top = 0;
int cp = i + 1;
rep(j,i+2,n+1) {
while (cp < j and f[i][cp][1] < f[cp][j][0]) {
mxl = max(mxl, f[i][cp][1] + 1ll * (s[cp] - s[i]) * (s[cp] - s[i]) + d[cp]);
lhull.addr(cp, f[i][cp][1] + 1ll * s[cp] * s[cp] + d[cp]);
++ cp;
}
while (p[j] > cp) {
-- p[j];
mxr[j] = max(mxr[j], f[p[j]][j][0] + 1ll * (s[j] - s[p[j]]) * (s[j] - s[p[j]]) + d[p[j]]);
rhull[j].addl(p[j], f[p[j]][j][0] + 1ll * s[p[j]] * s[p[j]] + d[p[j]]);
}
f[i][j][0] = max(mxl, rhull[j].query(2 * s[i]) + 1ll * s[i] * s[i]);
f[i][j][1] = max(mxr[j], lhull.query(2 * s[j]) + 1ll * s[j] * s[j]);
}
} cout << f[0][n + 1][0] << '\n';
}
T3
题目是最短路板子，那我们就用最短路板子做这题。
先把树剖了。随后考虑线段树优化 dij，我们把堆换成线段树，用来维护 dis 数组。然后一般化地把树边也在过程中维护。
两种加边操作都可以在 dfn 序上自然完成，写的时候可以直接暴力递归到叶子。
总时间复杂度是均摊的 \(O(m\log n)\)？
题解是通过 gbt 和三度化得到的大常数 \(O(m\log n)\) 做法。
类似的题还有 bzoj4699。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, m, t1, t2, t3, t4, t5;
priority_queue<pair<ll, int>> que;
vp g[N];
struct info {
int typ, u, v, w;
}; vector<info> gr[N];
int dep[N], fa[N], top[N], siz[N], son[N], dfn[N], ed[N], idfn[N], stp;
ll dis[N];
void dfs1(int u, int ft) {
dep[u] = dep[ft] + 1, fa[u] = ft;
siz[u] = 1, son[u] = 0;
for (auto [v, w] : g[u]) if (v != ft) {
dis[v] = dis[u] + w, dfs1(v, u);
siz[u] += siz[v];
if (siz[v] >= siz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp) {
dfn[u] = ++ stp, idfn[stp] = u, top[u] = tp;
if (son[u]) dfs2(son[u], tp);
for (auto [v, w] : g[u]) if (v != fa[u] and v != son[u])
dfs2(v, v);
ed[u] = stp;
}
struct sgt {
#define ls (p << 1)
#define rs (p << 1 | 1)
ll seg[N << 2];
void build(int p, int l, int r) {
if (l == r) return void(seg[p] = (l == 1 ? 0 : 1e17));
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
seg[p] = max(seg[ls], seg[rs]);
}
void updatemin(int p, int l, int r, int L, int R, int va) {
if (va >= seg[p]) return;
if (l == r) return que.emplace(- (dis[idfn[l]] = seg[p] = va), idfn[l]), void();
int mid = l + r >> 1;
if (L <= mid) updatemin(ls, l, mid, L, R, va);
if (mid < R) updatemin(rs, mid + 1, r, L, R, va);
seg[p] = max(seg[ls], seg[rs]);
}
} Tr;
void update(int u, int v, int w) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
Tr.updatemin(1, 1, n, dfn[top[u]], dfn[u], w);
u = fa[top[u]];
} if (dep[u] > dep[v]) swap(u, v);
Tr.updatemin(1, 1, n, dfn[u], dfn[v], w);
}
bool vis[N];
void dij() {
rep(i,1,n) dis[i] = 1e16;
dis[1] = 0; que.emplace(0, 1);
while (que.size()) {
int u = que.top().second; que.pop();
if (vis[u]) continue; vis[u] = 1;
for (auto [v, w] : g[u]) if (dis[v] > dis[u] + w) {
Tr.updatemin(1, 1, n, dfn[v], dfn[v], dis[u] + w);
} for (auto it : gr[u]) {
if (it.typ == 1) update(it.u, it.v, dis[u] + it.w);
else Tr.updatemin(1, 1, n, dfn[it.u], ed[it.u], dis[u] + it.w);
}
}
}
signed main() {
file(path);
cin >> n >> m;
rep(i,2,n) cin >> t1 >> t2 >> t3, g[t1].eb(t2, t3), g[t2].eb(t1, t3);
dfs1(1, 0), dfs2(1, 1);
Tr.build(1, 1, n);
rep(i,1,m) {
cin >> t1;
if (t1 == 1) cin >> t2 >> t3 >> t4 >> t5, gr[t2].push_back( { 1, t3, t4, t5 } );
else cin >> t2 >> t3 >> t4, gr[t2].push_back( { 2, t3, 0, t4 } );
} dij();
rep(i,1,n) cout << dis[i] << '\n';
}
杂题
怎么全是莫队？
给定 \(n,m\) 以及一个长为 \(n\) 的序列 \(a\)。有 \(m\) 组询问，每组询问给出 \(l,r\)，你需要求出：对 \(\in [l,r]\) 且满足 \(i \neq j\) 的 \(i, j\)，\(|a_i-a_j|\) 的最小值。
\(1 \leq n \leq 10^5\)，\(1 \leq m \leq 3\times 10^5\)，\(0 \leq a_i \leq 10^9\)。
考虑怎么用 set 暴力。我们写一个不删莫队，这样每次加入元素后只需要查询它的前驱后继更新答案就可以了。
总时间复杂度 \(O(n\sqrt n \log n)\)。过不去。
等等……前驱后继？我们离散化，这样值域是 \(O(n)\) 的了。写一个压位 Trie 或 vEB 树即可通过。
总时间复杂度 \(O(n\sqrt n\log_w n)\)。过得去。
正解是 \(O(n\log n\log V)\) 的。
考虑对每个 \(r\) 维护 \(ans(i) = \min_{j = i + 1}^r \left\lvert a_i - a_j\right\rvert\)。那么我们对 \((l, r)\) 的询问，只需要查询一段后缀最小值即可。
考虑在 \(r - 1\to r\) 的过程中如何维护 \(ans\)。我们其实无需严格地按上方的定义维护 \(ans\)，只需要让后缀最小值是答案即可。这样我们总共要修改的位置就被缩减到了 \(O(n \log V)\) 个。为什么呢？
我们讨论 \(a_r\) 对一对 \((i, j)\) 的贡献。如果 \(a_r \le \left\lfloor\frac{a_i + a_j}2\right\rfloor\)，我们可以直接修改 \(ans(i)\)，并且 \(ans(i)\) 被减小了至少一半。反之我们可以在 \(ans(j)\) 处再修改，因为答案一定不会在 \(ans(i)\) 处取得。这样可以证明修改的点是 \(O(n\log V)\) 的。使用线段树维护一下能得到 \(O(n\log n\log V)\) 的复杂度。
没写代码。
有一个长为 \(n\) 的数组，进行 \(m\) 次询问，每次为以下两种中的一种：
1 l r k：给定区间 \([l,r]\)，你需要求出最小的 \(\text{dif}\)，使得能够选出 \(k\) 个互不相同的数 \(a_1,a_2,\cdots,a_k\)，令这些数在区间中的出现次数分别为 \(cnt_1,cnt_2,\cdots,cnt_k\)（任意 \(cnt_i > 0\)），则 \(\text{dif}\) 为这些 \(cnt_i\) 的极差；若无法选出 \(k\) 个数，则输出 \(-1\).
2 p x：将位置 \(p\) 赋值为 \(x\)。输入的所有数值域 \([1,10^5]\)。
这个询问一看就有 bear 来，考虑带修莫队。
考虑维护一个当前区间元素出现次数的桶 \(b_1\)，并用链表形式维护这个桶的桶 \(b_2\)。
插入删除考虑维护 \(b_1\) 每个元素的值对应的 \(b_2\) 的节点，这样插入删除是 \(O(1)\) 的。
查询答案考虑将 \(b_2\) 放到数组里，用双指针即可求得答案。第二部分由于是桶的桶，出现元素个数总不会超过 \(O(\sqrt n)\)，证明考虑 \(\sum_{i = 1}^k i \ge n\) 的最小 \(k\) 是 \(O(\sqrt n)\) 量级的。
总时间复杂度 \(O(n^{5/3} + n^{3/2})\)。
其实第二部分用数组暴力扫是可以过的，要卡掉其实很容易。
这个是假做法的代码：Submission
链表写法还 RE 着呢。