TPOI T1 题解

Register_int · 2025-06-11 06:55:21 · 题解

考察你是否记得 \operatorname{mex} 的定义。

由定义，\operatorname{mex} 就是补集 \min，于是可以发现 \operatorname{mex}(q_{l\sim r})=\min(a_{l-1},b_{r+1})，也就是说所有排列的权值都是一样的。所以你只需要算权值和方案数再乘起来。

老套路把 \sum_{l\le r}\operatorname{mex}(q_l,q_{l+1},\cdots,q_r) 拆成 \sum_{k}\sum_{l\le r}[\forall 0\le i\le k,i\in \{q_l,q_{l+1},\cdots,q_r\}]。那么先找出所有确定的数，维护他们的逆排列，枚举 \operatorname{mex} 的值，即可算出当前 \operatorname{mex} 能填的位置范围、个数，以及哪些区间会对权值造成贡献。时间复杂度 O(n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll; 

const int MAXN = 2e5 + 10;
const int mod = 998244353;

inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }

int T, n, m, a[MAXN], b[MAXN], p[MAXN], q[MAXN], sum, tot;

int main() {
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &n), *a = b[n + 1] = -1, sum = 0, tot = 1;
        for (int i = 1; i <= n; i++) p[i] = -1;
        for (int i = 0; i < n; i++) q[i] = -1;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
        for (int i = 1; i <= n; i++) if (a[i] != a[i - 1]) p[i] = a[i];
        for (int i = 1; i <= n; i++) if (b[i] != b[i + 1]) p[i] = b[i];
        for (int i = 1; i <= n; i++) if (~p[i]) q[p[i]] = i - 1;
        for (int i = 0, l = *q, r = *q; i < n; i++) {
            if (~q[i]) l = min(l, q[i]), r = max(r, q[i]);
            else tot = (ll)tot * (r - l + 1 - i) % mod;
            cadd(sum, (ll)(l + 1) * (n - r) % mod);
        }
        printf("%lld\n", (ll)sum * tot % mod);
    }
}