Public Round 15 前两题
2025-02-16

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(即归并排序)地求解答案。

#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;
}

一言 - Hitokoto