PR #15 前两题题解。
最小表示法
https://pjudge.ac/contest/1914/problem/21888
首先不妨假设每个 \(f\) 在值域内等概率取值以简化问题。那么手玩一下可以轻松地得到规律：不妨将 \(\{s\}\) 循环右移一位的结果记为 \(\{t\}\)，那么 \(res=\sum\frac 1{\max(|s_i|,|t_i|)}\)。
这看起来令人疑惑：对于不同的 \(i\)，\([f(s_i)=f(t_i)]\) 的期望似乎是彼此独立的，十分奇怪。这其实与表达式的来源有关，记 \(g(s_i, j)\) 表示 \(f(s_i)=j\) 的概率，那么上述等式可以转写为 \(res=\sum\limits_i\sum\limits_jg({s_i},j)\times g(t_i,j)\)。
那么将最小表示法带来的偏差纳入考虑范围，我们发现 \(g(s,j)\) 对于不同的 \(j\) 并不永远相等。具体地，当 \(s\) 具有循环节时，最小循环节的第一处结尾会享有更大的取得概率。
枚举 \(s_i\) 的因数作为最小循环节长度的情况，显然，对于最小循环节为 \(j\) 的情况（该情况出现的概率，容斥得到 \(p_j=26^j-\sum_{k\mid j}p_k\)），\(f(s_i)\) 的取值在 \(1\sim j\) 上等概率分布，差分即可统计每个值在不同循环节长度下被取到的概率和。
用埃筛解决每个数的因数和 \(p\) 值，那么此时复杂度瓶颈在于 \(g(s_i, j)\) 和 \(\sum\limits_i\sum\limits_jg({s_i},j)\times g(t_i,j)\) 的求解。容易发现只有每个 \(g(s_i,j),j\mid |s_i|\) 的值是有效的（其他的和它们值都相同），考虑只求解和利用这些值，类 std::merge（即归并排序）地求解答案。
注意特判 \(n=1\)。会得到错误答案的原因是此时存在 \(s_i=t_i\)，不满足基本要求。
#include <bits/stdc++.h>
const int lim = 1e5;
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
if (n == 1) {
std::cout << 1 << '\n';
return 0;
}
auto qkp = [](long long x, int y) {
long long res = 1ll;
for (; y; y >>= 1, (x *= x) %= mod)
if (y & 1)
(res *= x) %= mod;
return res;
};
auto inv = [&](int x) {
return qkp(x, mod - 2);
};
std::vector<long long> f(lim + 1);
std::vector<std::vector<int> > fac(lim + 1);
for (int i = 1; i <= lim; ++i) {
static long long now = 26;
(f[i] += now) %= mod;
fac[i].push_back(i);
for (int j = 2 * i; j <= lim; j += i)
(f[j] += mod - f[i]) %= mod, fac[j].push_back(i);
(now *= 26) %= mod;
}
for (int i = 1; i <= lim; ++i)
(f[i] *= inv(i)) %= mod;
std::vector<int> a(n + 1);
struct _ { int l, r; long long f; };
std::vector<std::vector<_> > g(lim + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
if (g[a[i]].empty()) {
g[a[i]].resize(fac[a[i]].size());
for (int j = 0; j < (int)fac[a[i]].size(); ++j) {
g[a[i]][j].l = (j ? g[a[i]][j - 1].r + 1 : 1);
g[a[i]][j].r = fac[a[i]][j];
(g[a[i]][0].f += f[fac[a[i]][j]]) %= mod;
if (j != (int)fac[a[i]].size() - 1)
(g[a[i]][j + 1].f += mod - f[fac[a[i]][j]]) %= mod;
}
for (int j = 1; j < (int)fac[a[i]].size(); ++j)
(g[a[i]][j].f += g[a[i]][j - 1].f) %= mod;
int getinv = inv(qkp(26, a[i]));
for (int j = 0; j < (int)fac[a[i]].size(); ++j)
(g[a[i]][j].f *= getinv) %= mod;
}
}
std::vector<int> b(n + 1);
std::rotate_copy(a.begin() + 1, --a.end(), a.end(), b.begin() + 1);
long long res = 0ll;
for (int i = 1; i <= n; ++i) {
for (int j = 0, k = 0, now = 0;
j < (int)fac[a[i]].size() && k < (int)fac[b[i]].size(); )
if (g[a[i]][j].r < g[b[i]][k].r) {
(res += g[a[i]][j].f * g[b[i]][k].f % mod
* (g[a[i]][j].r - now) % mod) %= mod;
now = g[a[i]][j].r, ++j;
}
else if (g[a[i]][j].r == g[b[i]][k].r) {
(res += g[a[i]][j].f * g[b[i]][k].f % mod
* (g[a[i]][j].r - now) % mod) %= mod;
now = g[a[i]][j].r, ++j, ++k;
}
else {
(res += g[a[i]][j].f * g[b[i]][k].f % mod
* (g[b[i]][k].r - now) % mod) %= mod;
now = g[b[i]][k].r, ++k;
}
}
std::cout << res << '\n';
return 0;
}二叉搜索树
https://pjudge.ac/contest/1914/problem/21889
当我们处理链的部分分时，很容易想到用差分解决问题。把更新 \([l, r]\) 看作在差分数组 \(l\) 处插入，在 \(r+1\) 处删除，离线下来再从左到右扫一遍操作，考虑如何解决查询问题。
考虑如何获取 \(i\) 树上 \(t_0\) 时刻点 \(x\) 的所有祖先。根据前面的操作，我们可以获取 \(i\) 树上存在过的所有元素。
对于比 \(x\) 大的元素，考虑祖先 \(p_a\) 和非祖先 \(p\) 有什么区别。根据 BST 的性质易得，对于最低的右侧祖先 \({p_a}_0\)，其是 \(\ge x\) 的最小的元素（当然其加入时刻 \(t_a<t_0\)）；那么同理可以找到 \({p_a}_0\) 右侧最低的祖先（其左侧的祖先显然也 \(x\) 左侧），该祖先满足 \(t<t_a\)。那么我们就从左右两边分别得到 \(x\) 的所有祖先。容易证明该过程对于不在树上的 \(x\) 也是正确的。
具体地，我们需要一个数据结构，能够求出 \(\ge x\) 的元素中，以 \(t_0\) 为起点的前缀最小值序列的区间和。
欸 ☝🤓 这是什么？楼房重建！秒一下！
进一步地，本题需要完成对于 \(t_0\) 为序列头的查询。再次利用性质，每次 \(O(\log V)\) 地合并答案。
好的那么怎么把链搞到树上呢？把差分放到树上，写个线段树合并即可。
注意由于这题细节太多了，所以你可能需要舍弃不必要的时空优化换取代码简洁度以方便调试。
#include <bits/stdc++.h>
const int lim = 2e5;
const int maxn = 2e7 + 5;
const int inf = 0x3f3f3f3f;
struct {
int l, r, rv;
long long u;
} t[maxn];
std::vector<int> tr;
#define lt t[p].l
#define rt t[p].r
int newnode(void) { // 我知道你要说什么，但这属于「必要的」空间优化 😥
static int tot = 0;
if (tr.empty())
return ++tot;
auto p(tr.back());
t[p].l = t[p].r = 0;
tr.pop_back();
return p;
}
long long askv(int p, int l, int r, int v) {
if (l == r)
return t[p].rv < v ? t[p].u : 0;
int mid = (l + r) >> 1;
if (v > t[lt].rv)
return t[p].u - t[lt].u + askv(lt, l, mid, v);
return askv(rt, mid + 1, r, v);
}
void pushup(int p, int l, int r) {
t[p].rv = std::min(t[lt].rv, t[rt].rv);
int mid = (l + r) >> 1;
t[p].u = t[lt].u + askv(rt, mid + 1, r, t[lt].rv);
return;
}
void upd(int &p, int l, int r, int x, int v, int u) {
if (!p)
p = newnode();
if (l == r) {
t[p].rv = v, t[p].u = u;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
upd(lt, l, mid, x, v, u);
else
upd(rt, mid + 1, r, x, v, u);
pushup(p, l, r);
return;
}
void merge(int &p, int q, int l, int r) {
if (!p || !q) {
p += q;
return;
}
if (l == r) {
t[p].rv = std::min(t[p].rv, t[q].rv);
t[p].u = std::max(t[p].u, t[q].u);
return;
}
int mid = (l + r) >> 1;
merge(t[p].l, t[q].l, l, mid), merge(t[p].r, t[q].r, mid + 1, r);
pushup(p, l, r), tr.push_back(q);
return;
}
int qv = inf;
long long ask(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
auto s(askv(p, l, r, qv));
qv = std::min(qv, t[p].rv);
return s;
}
int mid = (l + r) >> 1;
long long res = 0ll;
if (ql <= mid)
res = ask(lt, l, mid, ql, qr);
if (qr > mid)
res += ask(rt, mid + 1, r, ql, qr);
return res;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("ex_problem4.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> top(n + 1), fa(n + 1), siz(n + 1), son(n + 1), dep(n + 1);
std::function<void(int, int)> DFS = [&](int x, int faa) {
siz[x] = 1;
for (auto i : g[x])
if (i != faa) {
fa[i] = x, dep[i] = dep[x] + 1;
DFS(i, x), siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
};
DFS(1, -1);
DFS = [&](int x, int topp) {
top[x] = topp;
if (son[x])
DFS(son[x], topp);
for (auto i : g[x])
if (i != fa[x] && i != son[x])
DFS(i, i);
return;
};
DFS(1, 1);
auto getLCA = [&](int x, int y) {
for (; top[x] != top[y]; x = fa[top[x]])
if (dep[top[y]] > dep[top[x]])
std::swap(x, y);
return (dep[x] < dep[y] ? x : y);
};
std::vector<std::vector<int> > d(n + 1);
std::vector<std::vector<std::pair<int, int> > > u(n + 1);
std::vector<std::vector<std::tuple<int, int, int> > > q(n + 1);
int cnt = 0;
for (int i = 1; i <= m; ++i) {
int op;
std::cin >> op;
if (op == 0) {
int x, v;
std::cin >> x >> v;
q[x].emplace_back(++cnt, i, v);
} else {
int x, y, v;
std::cin >> x >> y >> v;
int faa = getLCA(x, y);
u[x].emplace_back(i, v), u[y].emplace_back(i, v);
if (fa[faa])
d[fa[faa]].emplace_back(v);
}
}
std::vector<long long> res(cnt + 1);
std::vector<std::vector<int> > rt(2, std::vector<int> (n + 1));
t[0].rv = inf;
DFS = [&](int x, int fa) {
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
merge(rt[0][x], rt[0][i], 1, lim);
merge(rt[1][x], rt[1][i], 1, lim);
}
for (auto [t, v] : u[x]) {
upd(rt[0][x], 1, lim, v, t, v);
upd(rt[1][x], 1, lim, lim - v + 1, t, v);
}
for (auto v : d[x]) {
upd(rt[0][x], 1, lim, v, inf, 0);
upd(rt[1][x], 1, lim, lim - v + 1, inf, 0);
}
for (auto [id, t, v] : q[x]) {
qv = t, res[id] = ask(rt[0][x], 1, lim, v, lim);
qv = t, res[id] += ask(rt[1][x], 1, lim, lim - v + 1, lim);
qv = t, res[id] -= ask(rt[0][x], 1, lim, v, v);
}
};
DFS(1, -1);
for (int i = 1; i <= cnt; ++i)
std::cout << res[i] << '\n';
return 0;
}