260223 模拟赛

T1

给定一个长为 \(n\) 的排列 \(A\)，问有多少个长为 \(n\) 的排列 \(B\) 满足 \(B\) 的字典序大于 \(A\) 并且 \(B\) 可以用一个栈重排成单位排列。

\(n\le 10^6\)

如果没有 \(A\) 的限制那么答案显然是卡特兰数。否则，考虑钦定 \(B\) 的一个前缀与 \(A\) 相等，然后下一位更大。

\(A_1\) 到 \(A_i\) 这 \(i\) 个数将值域划分成了若干连续段（连续没出现过的数构成的段），注意到这些段必须按顺序出现，否则不合法。于是如果不管 \(b_{i+1}>a_{i+1}\) 的限制，\(b\) 的后缀就是一些独立的子问题，方案数是一些卡特兰数的乘积。

如果加上这个限制，那么就是要求一个 \(f_{n,k}=\sum_{i=1}^{k}f_{i-1}f_{n-i}\) 状物，求一次是 \(O(k)\) 的。发现 \(f_{n,k}\) 也可以通过减去另一半做到 \(O(n-k)\)。猜测暴力做复杂度就是对的，注意到求一次 \(f_{n,k}\) 之后就会插入 \(a_{i+1}\) 把刚刚的区间从 \(k\) 的位置切成两半，也就是说直接 \(O(\min(k,n-k))\) 启发式分裂做就是对的。时间复杂度 \(O(n\log n)\)。

代码

#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
const int MOD = 998244353;

inline void read(int &x) {
    char ch;
    while(!isdigit(ch = getchar_unlocked()));
    x = ch - '0';
    while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
}
inline void write(int x) {
    char buf[60], top = 0;
    do buf[++top] = x % 10 + '0', x /= 10; while(x);
    while(top) putchar_unlocked(buf[top--]);
}

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }
inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = (ll)res * a % MOD;
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

int n, lim, val, ans;
int inv[N], fac[N], ifac[N];
int a[N], f[N], vis[N];

inline int C(int a, int b) { return (ll)fac[a] * ifac[b] % MOD * ifac[a - b] % MOD; }
inline int g(int n, int k) {
    int res = 0;
    if(k < n / 2) {
        for(int i = 1; i <= k; i++) add(res, (ll)f[i - 1] * f[n - i] % MOD);
    } else {
        res = f[n];
        for(int i = k + 1; i <= n; i++) add(res, MOD - (ll)f[i - 1] * f[n - i] % MOD);
    }
    return res;
}

set<int> st;

int main() {

    freopen("stack.in", "r", stdin);
    freopen("stack.out", "w", stdout);

    inv[1] = fac[0] = ifac[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - (ll)inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifac[i] = (ll)ifac[i - 1] * inv[i] % MOD;

    f[0] = 1;
    for(int i = 1; i < N / 2; i++) f[i] = (C(2 * i, i) - C(2 * i, i - 1) + MOD) % MOD;

    read(n);
    st.insert(0); st.insert(n + 1);
    for(int i = 1; i <= n; i++) read(a[i]);
    val = f[n];
    for(int i = 0, mex = 1; i <= n; i++) {
        if(i) {
            auto tmp = st.lower_bound(a[i]);
            int nxt = *tmp, pre = *--tmp;
            val = (ll)val * qpow(f[nxt - pre - 1], MOD - 2) % MOD;
            val = (ll)val * f[a[i] - pre - 1] % MOD;
            val = (ll)val * f[nxt - a[i] - 1] % MOD;
            lim = max(lim, pre);
            st.insert(a[i]); vis[a[i]] = 1;
        }
        while(vis[mex]) ++mex;
        if(mex < lim) break;
        if(i == n) add(ans, val);
        else {
            int L = mex;
            int R = *st.lower_bound(L) - 1;
            if(a[i + 1] >= R) continue;
            if(a[i + 1] < L) add(ans, val);
            else {
                int tmp = val;
                tmp = (ll)tmp * qpow(f[R - L + 1], MOD - 2) % MOD;
                tmp = (ll)tmp * g(R - L + 1, R - a[i + 1]) % MOD;
                add(ans, tmp);
            }
        }
    }

    write(ans);

    return 0;
}

T2

给定一个无向连通图，没有自环，可能有重边。你需要选择一条不经过重复边，从 \(1\) 出发的路径，最小化路径边权 \(\min+\max\)。你需要对每个点作为路径终点时求出答案。

\(n\le 3\times 10^5\)

扫描 \(\max\)，把边按照边权升序排列，然后一条一条加。我们需要动态维护一个边双树，加边会产生两种操作：在两个连通块之间加一个桥，以及将一条链上的所有点合并成一个边双。注意到边双树上的桥都是最小生成树上的边，因此我们直接在最小生成树上做，会方便很多。

合并边双可以用并查集维护，取边双中深度最小的点为代表元，这样暴力跳链的复杂度就是对的。合并之后会更新一个子树的 \(\min\)，这可以用线段树简单维护。加边时，如果边的一端是 \(1\) 所在的连通块，就暴力把另一端的连通块扫一遍，更新 \(\min\) 和 \(ans\)（为了不用从根一路跑下来，需要单点查询 \(mn\)，因次需要用两棵线段树分别维护 \(mn\) 和 \(ans\)）。时间复杂度 \(O(n\log n)\)。

代码

#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
const int INF = 0x7fffffff;

inline void gmin(int &a, int b) { a = min(a, b); }
inline void gmin(ll &a, ll b) { a = min(a, b); }

struct Node {
    int v, w, next;
} pool[2 * N];
int ne, head[N];
inline void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

struct Edge2 {
    int u, v, w;
} edg[N];

int n, m;
int fa1[N], mn[N]; ll ans[N];
bool mst[N], ok[2 * N], flag[N];
inline int find(int x) { if(fa1[x] == x) return x; return fa1[x] = find(fa1[x]); }
inline void merge(int x, int y) { fa1[find(x)] = find(y); }
int fa[N], fw[N], dep[N], dfn[N], id[N], sz[N], dt;

namespace SegT1 {
    struct Node {
        int tag1, tag2;
        inline Node() : tag1(0), tag2(INF) {}
        inline Node(int _t1, int _t2) : tag1(_t1), tag2(_t2) {}
    } tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_down(int p) {
        if(tr[p].tag1) tr[lc(p)] = tr[rc(p)] = {1, INF};
        if(tr[p].tag2 != INF) gmin(tr[lc(p)].tag2, tr[p].tag2), gmin(tr[rc(p)].tag2, tr[p].tag2);
        tr[p] = {0, INF};
    }
    void ckmin(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) return gmin(tr[p].tag2, v);
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) ckmin(lc(p), l, mid, ql, qr, v);
        if(mid < qr) ckmin(rc(p), mid + 1, r, ql, qr, v);
    }
    void clear(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return tr[p].tag1 = 1, tr[p].tag2 = INF, void();
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) clear(lc(p), l, mid, ql, qr);
        if(mid < qr) clear(rc(p), mid + 1, r, ql, qr);
    }
    void print(int p, int l, int r) {
        if(l == r) return gmin(ans[id[l]], tr[p].tag2), void();
        int mid = (l + r) >> 1; push_down(p);
        print(lc(p), l, mid); print(rc(p), mid + 1, r);
    }
}
namespace SegT2 {
    struct Node {
        int tag1, tag2;
        inline Node() : tag1(0), tag2(INF) {}
        inline Node(int _t1, int _t2) : tag1(_t1), tag2(_t2) {}
    } tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_down(int p) {
        if(tr[p].tag1) tr[lc(p)] = tr[rc(p)] = {1, INF};
        if(tr[p].tag2 != INF) gmin(tr[lc(p)].tag2, tr[p].tag2), gmin(tr[rc(p)].tag2, tr[p].tag2);
        tr[p] = {0, INF};
    }
    void ckmin(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) return gmin(tr[p].tag2, v);
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) ckmin(lc(p), l, mid, ql, qr, v);
        if(mid < qr) ckmin(rc(p), mid + 1, r, ql, qr, v);
    }
    void clear(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return tr[p].tag1 = 1, tr[p].tag2 = INF, void();
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) clear(lc(p), l, mid, ql, qr);
        if(mid < qr) clear(rc(p), mid + 1, r, ql, qr);
    }
    int query(int p, int l, int r, int q) {
        if(l == r) return tr[p].tag2;
        int mid = (l + r) >> 1; push_down(p);
        if(q <= mid) return query(lc(p), l, mid, q);
        return query(rc(p), mid + 1, r, q);
    }
}

void dfs1(int u) {
    dfn[u] = ++dt; id[dt] = u;
    sz[u] = 1; dep[u] = dep[fa[u]] + 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa[u]) continue;
        fa[v] = u; fw[v] = w;
        dfs1(v);
        sz[u] += sz[v];
    }
}
void dfs2(int u, int pre, int mx) {
    pre = min(pre, mn[find(u)]);
    SegT2::ckmin(1, 1, n, dfn[u], dfn[u], pre);
    ans[u] = min(ans[u], (ll)pre + mx);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa[u] || !ok[e]) continue;
        dfs2(v, min(pre, w), mx);
    }
}

int main() {

    freopen("alley.in", "r", stdin);
    freopen("alley.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> edg[i].u >> edg[i].v >> edg[i].w;
    sort(edg + 1, edg + 1 + m, [](Edge2 a, Edge2 b){ return a.w < b.w; });
    for(int i = 1; i <= n; i++) fa1[i] = i, ans[i] = mn[i] = INF;
    for(int i = 1; i <= m; i++) {
        int u = edg[i].u, v = edg[i].v, w = edg[i].w;
        if(find(u) == find(v)) continue;
        addEdge(u, v, w);
        addEdge(v, u, w);
        merge(u, v); mst[i] = 1;
        if(find(u) == find(1)) flag[i] = 1;
    }
    dfs1(1);
    for(int i = 1; i <= n; i++) fa1[i] = i;
    for(int i = 1, cnt = 0; i <= m; i++) {
        int u = edg[i].u, v = edg[i].v, w = edg[i].w;
        if(mst[i]) {
            ++cnt; ok[2 * cnt - 1] = ok[2 * cnt] = 1;
            if(!flag[i]) continue;
            if(dep[u] > dep[v]) swap(u, v);
            SegT1::clear(1, 1, n, dfn[v], dfn[v] + sz[v] - 1);
            SegT2::clear(1, 1, n, dfn[v], dfn[v] + sz[v] - 1);
            int tmp = min(SegT2::query(1, 1, n, dfn[u]), w);
            dfs2(v, tmp, w);
        } else {
            int tmp = INF;
            while(u != v) {
                if(dep[u] < dep[v]) swap(u, v);
                tmp = min(tmp, min(mn[find(u)], fw[u]));
                merge(u, fa[u]);
                u = find(u);
            }
            mn[u] = min(mn[u], tmp);
            assert(find(u) == u);
            SegT1::ckmin(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, w + mn[u]);
            SegT2::ckmin(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, mn[u]);
        }
    }
    SegT1::print(1, 1, n);
    for(int i = 2; i <= n; i++) cout << ans[i] << '\n';

    return 0;
}