区间Mex（困难版本） - 题解

标签与难度

标签: 数学, 组合计数, 分治, 贡献法, 前缀和, 快速幂, 数据结构难度: 2700

题目大意喵~

哈喵~！各位算法大师们，今天我们来挑战一道有点意思的数学题哦！

题目给了我们一个长度为 $n$ 的排列（也就是 $1$ 到 $n$ 不重不漏地出现一次）。对于这个排列的任意一个连续子数组 $a[i..j]$ ，我们要计算一个叫做 mex 的东西。mex(i, j) 指的是这个子数组中，没有出现的最小正整数。比如说，对于子数组 {3, 1, 4}，它没出现过的最小正整数是 $2$ ，所以 mex 就是 $2$ 啦。

然后，我们定义一个值 $t(i, j) = (j - i + 1) \times \text{mex}(i, j)$ ，也就是子数组的长度乘以它的 mex 值。

我们的最终目标，是计算下面这个超级大的和 F(a)：

F(a) = \sum_{i=1}^{n} \sum_{j=i}^{n} 2^{t(i,j)} \times t(i,j)

因为结果会非常非常大，所以要对 $998244353$ 取模。

这还没完呢！这可是困难版本哦！接下来会有 $q$ 次独立的询问。每次询问会给你两个值 $x$ 和 $y$ ，你需要先把原数组中值为 $x$ 和 $y$ 的两个元素交换位置，然后计算新排列的 $F(a')$ 值。每次询问都是独立的，意味着下一次询问前，数组会恢复原样。

解题思路分析

喵呜~ 看到这个 $2^{t(i,j)} \times t(i,j)$ 的求和式，直接暴力枚举所有子数组肯定是行不通的，时间会爆炸的！( $N, Q \le 200000$ )。这种时候，我们就要转变思路，从“贡献”的角度来思考问题，呐。

我们可以不枚举子数组，而是枚举 mex 的值，然后计算所有 mex 等于这个值的子数组产生的贡献之和。

总的答案可以写成：

F(a) = \sum_{m=1}^{n+1} C(m)

其中 $C(m)$ 表示所有满足 $\text{mex}(i, j) = m$ 的子数组 $[i, j]$ 的贡献总和。

C(m) = \sum_{\substack{1 \le i \le j \le n \\ \text{mex}(i,j)=m}} m \cdot (j-i+1) \cdot 2^{m \cdot (j-i+1)}

怎么找到 `mex` 等于 $m$ 的子数组呢？

一个子数组 $[i, j]$ 的 mex 值等于 $m$ ，必须满足两个条件：

子数组中包含了所有 $1, 2, \dots, m-1$ 这些数。
子数组中 不包含 数字 $m$ 。

为了方便处理，我们先预处理出每个数值 $v$ 在排列 $a$ 中的位置，记为 $\text{pos}[v]$ 。然后，我们定义 $L_k = \min_{v=1 \dots k} \{\text{pos}[v]\}$ 和 $R_k = \max_{v=1 \dots k} \{\text{pos}[v]\}$ 。 $L_k$ 和 $R_k$ 分别是数值 $1$ 到 $k$ 在数组中出现的最左和最右的位置。

那么，条件1就可以转化为：子数组 $[i, j]$ 必须完全覆盖区间 $[L_{m-1}, R_{m-1}]$ 。也就是说，子数组的左右端点需要满足 $1 \le i \le L_{m-1}$ 且 $R_{m-1} \le j \le n$ 。

条件2就是，区间 $[i, j]$ 不能包含位置 $\text{pos}[m]$ 。

把这两个条件合起来，我们就能确定所有 mex 为 $m$ 的子数组 $[i, j]$ 的范围了。

计算贡献 $C(m)$

喵~ 这里的数学推导有点小复杂，但别怕，我们一步步来解剖它！

情况一：m = 1 $\text{mex}(i, j) = 1$ 意味着数字 $1$ 不在子数组 $[i, j]$ 中。设 $\text{pos}[1]$ 是数字 $1$ 的位置。那么，这个子数组要么完全在 $\text{pos}[1]$ 的左边（即 $j < \text{pos}[1]$ ），要么完全在右边（即 $i > \text{pos}[1]$ ）。这相当于把原数组分成了两段独立的区域： $[1, \text{pos}[1]-1]$ 和 $[\text{pos}[1]+1, n]$ 。我们只需要分别计算这两段区域内所有子数组的贡献，然后加起来就是 $C(1)$ 了。

对于一个长度为 $W$ 的连续段，其贡献和为：

S(W) = \sum_{k=1}^{W} (W-k+1) \cdot k \cdot 2^k

这里 $k$ 是子数组长度， $(W-k+1)$ 是长度为 $k$ 的子数组的个数。这个式子可以通过预处理 $\sum i \cdot 2^i$ 和 $\sum i^2 \cdot 2^i$ 的前缀和来 $O(1)$ 计算。所以 $C(1) = S(\text{pos}[1]-1) + S(n-\text{pos}[1])$ 。

情况二：m > 1 设 $L = L_{m-1}$ , $R = R_{m-1}$ , $P = \text{pos}[m]$ 。我们要找的子数组 $[i,j]$ 满足 $1 \le i \le L$ , $R \le j \le n$ 且 $P \notin [i,j]$ 。

如果 $L \le P \le R$ ，那么任何满足 $i \le L, j \ge R$ 的区间 $[i,j]$ 都必然包含 $P$ 。这种情况下，不存在 mex 为 $m$ 的子数组， $C(m)=0$ 。
如果 $P < L$ 或者 $P > R$ ，我们以 $P < L$ 为例分析。由于 $j \ge R > L > P$ ，所以 $j>P$ 总是成立的。要让 $P \notin [i,j]$ ，我们只需要 $i > P$ 。所以，合法的 $(i,j)$ 对需要满足 $P < i \le L$ 和 $R \le j \le n$ 。

此时的贡献和为：

C(m) = \sum_{i=P+1}^{L} \sum_{j=R}^{n} m \cdot (j-i+1) \cdot 2^{m(j-i+1)}

这是一个关于 $i$ 和 $j$ 的双重求和。通过一些巧妙的代数变换（比如令 $i_{\text{off}} = L-i$ ， $j_{\text{off}} = j-R$ ），这个求和式可以变成一个可以用等比数列求和 (sum q^k) 和差比数列求和 (sum k*q^k) 的封闭形式来计算。具体的公式推导比较繁琐，但其本质就是将复杂的双重求和化简为几个预处理好的求和公式的组合，从而实现 $O(1)$ 计算。

处理查询

每次查询交换值 $x$ 和 $y$ 的位置（假设 $x<y$ ）。这会改变 $\text{pos}[x]$ 和 $\text{pos}[y]$ 。 $C(m)$ 的计算依赖于 $L_{m-1}, R_{m-1}$ 和 $\text{pos}[m]$ 。

当 $m \le x$ 时，计算 $C(m)$ 所需的 $L_{m-1}, R_{m-1}$ 不受交换影响。但如果 $m=x$ ， $\text{pos}[m]$ 会变，所以 $C(x)$ 需要重算。
当 $x < m \le y$ 时， $L_{m-1}, R_{m-1}$ 可能会因为 $\text{pos}[x]$ 的变化而改变。如果 $m=y$ ， $\text{pos}[y]$ 也会变。所以这些 $C(m)$ 都需要重算。
当 $m > y$ 时，集合 $\{1, \dots, m-1\}$ 同时包含了 $x$ 和 $y$ 。交换它俩的位置不改变这个集合的位置范围，即 $L_{m-1}$ 和 $R_{m-1}$ 不变。 $\text{pos}[m]$ 也不变。所以 $C(m)$ 不变。

综上，每次查询我们只需要重新计算 $m \in [x, y]$ 区间的贡献 $C(m)$ 即可。

我们可以先 $O(N)$ 预计算出初始排列的所有 $C(m)$ 和总答案 $F_0$ 。对于每次查询 $(x, y)$ ，我们计算出 $m \in [x, y]$ 的新旧贡献差值 $\Delta$ ，最终答案就是 $F_0 + \Delta$ 。

为了高效地计算交换后的 $L_k, R_k$ ，我们需要预处理出前 $k$ 个数中位置的第一小、第二小、第一大、第二大的值。这样在某个位置变化后，可以快速更新 $L_k$ 和 $R_k$ 。

总的来说，算法流程是：

预计算：计算 $2$ 的幂、模逆元、 $\sum i \cdot 2^i$ 和 $\sum i^2 \cdot 2^i$ 的前缀和。
初始化：计算初始排列的 pos 数组，以及前缀最小/最大位置（包括第二小/大）。
计算初始答案：循环 $m$ 从 $1$ 到 $n+1$ ，用上面推导的公式计算每个 $C(m)$ ，存起来，并求和得到初始总答案 $F_0$ 。
处理查询：对于每个查询 $(x, y)$ ，计算 $\Delta = \sum_{m=x}^{y} (C_{\text{new}}(m) - C_{\text{old}}(m))$ ，输出 $F_0 + \Delta$ 。

代码实现

这是我根据上面的思路，精心重构的一份代码~ 希望能帮到你哦！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

using int64 = long long;
const int MOD = 998244353;
const int MAXN = 200005;

// 快速幂，喵~
int64 power(int64 base, int64 exp) {
    int64 res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元，费马小定理yyds!
int64 modInverse(int64 n) {
    return power(n, MOD - 2);
}

int n;
vector<int> a(MAXN), pos(MAXN);

// 预计算的表
vector<int64> pow2(MAXN * MAXN);
vector<int64> inv_pow2m1(MAXN);

// 预计算前缀最小/最大位置
// mn1/mx1 是第一小/大, mn2/mx2 是第二小/大
vector<int> initial_mn1(MAXN), initial_mn2(MAXN);
vector<int> initial_mx1(MAXN), initial_mx2(MAXN);

// 存储每个mex的初始贡献
vector<int64> initial_contrib(MAXN);

// S(W) = sum_{k=1..W} (W-k+1) * k * 2^k
vector<int64> S1_prefix(MAXN), S2_prefix(MAXN);

// 计算长度为 len 的段中，mex=1 的贡献
int64 get_mex1_contrib_for_segment(int len) {
    if (len <= 0) return 0;
    int64 term1 = (int64)(len + 1) * S1_prefix[len] % MOD;
    int64 term2 = S2_prefix[len];
    return (term1 - term2 + MOD) % MOD;
}

// 计算贡献的核心函数
int64 calculate_contribution(int m, int L, int R, int p_m) {
    if (m > n + 1) return 0;
    
    // Case 1: mex = 1
    if (m == 1) {
        return (get_mex1_contrib_for_segment(p_m - 1) + get_mex1_contrib_for_segment(n - p_m)) % MOD;
    }

    // Case 2: mex > 1
    // 如果 m 的位置在 1..m-1 的位置范围内，贡献为0
    if (p_m >= L && p_m <= R) {
        return 0;
    }

    int64 q = pow2[m];
    int64 w = R - L + 1;
    int64 A, B;

    if (p_m < L) {
        A = L - p_m - 1;
        B = n - R;
    } else { // p_m > R
        A = L - 1;
        B = p_m - R - 1;
    }

    if (A < 0 || B < 0) return 0; // 不存在这样的区间

    int64 q_inv = inv_pow2m1[m];
    
    // sum_{k=0..len} q^k
    auto sum0 = [&](int64 len) {
        int64 q_len_plus_1 = power(q, len + 1);
        return (q_len_plus_1 - 1 + MOD) % MOD * q_inv % MOD;
    };
    
    // sum_{k=0..len} k * q^k
    auto sum1 = [&](int64 len) {
        int64 q_len_plus_1 = power(q, len + 1);
        int64 num1 = (len + 1) % MOD * q_len_plus_1 % MOD;
        int64 num2 = (q_len_plus_1 - 1 + MOD) % MOD * q_inv % MOD;
        int64 num = (num1 - num2 + MOD) % MOD;
        return num * q_inv % MOD;
    };

    int64 Sa0 = sum0(A);
    int64 Sb0 = sum0(B);
    int64 Sa1 = sum1(A);
    int64 Sb1 = sum1(B);

    int64 term1 = (w % MOD * Sa0 % MOD * Sb0) % MOD;
    int64 term2 = (Sa1 * Sb0) % MOD;
    int64 term3 = (Sa0 * Sb1) % MOD;
    int64 total_sum_part = (term1 + term2 + term3) % MOD;

    int64 res = (int64)m * power(q, w) % MOD * total_sum_part % MOD;
    return res;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    // --- 预计算 ---
    pow2[0] = 1;
    for (int i = 1; i <= n + 1; ++i) {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }
    for (int i = 1; i <= n + 1; ++i) {
        inv_pow2m1[i] = modInverse((pow2[i] - 1 + MOD) % MOD);
    }
    for (int k = 1; k <= n; ++k) {
        S1_prefix[k] = (S1_prefix[k - 1] + (int64)k * pow2[k]) % MOD;
        S2_prefix[k] = (S2_prefix[k - 1] + (int64)k * k % MOD * pow2[k]) % MOD;
    }

    // --- 初始化 ---
    const int INF = n + 2;
    initial_mn1[0] = INF; initial_mn2[0] = INF;
    initial_mx1[0] = 0;   initial_mx2[0] = 0;
    
    for (int v = 1; v <= n; ++v) {
        int p = pos[v];
        initial_mn1[v] = initial_mn1[v - 1]; initial_mn2[v] = initial_mn2[v-1];
        initial_mx1[v] = initial_mx1[v - 1]; initial_mx2[v] = initial_mx2[v-1];
        
        if (p < initial_mn1[v]) { initial_mn2[v] = initial_mn1[v]; initial_mn1[v] = p; } 
        else if (p < initial_mn2[v]) { initial_mn2[v] = p; }
        
        if (p > initial_mx1[v]) { initial_mx2[v] = initial_mx1[v]; initial_mx1[v] = p; } 
        else if (p > initial_mx2[v]) { initial_mx2[v] = p; }
    }

    int64 initial_total_sum = 0;
    for (int m = 1; m <= n + 1; ++m) {
        int L, R, p_m;
        if (m == 1) {
            L = INF; R = 0; p_m = pos[1];
        } else if (m <= n) {
            L = initial_mn1[m - 1]; R = initial_mx1[m - 1]; p_m = pos[m];
        } else { // m = n+1
            L = initial_mn1[n]; R = initial_mx1[n]; p_m = INF;
        }
        initial_contrib[m] = calculate_contribution(m, L, R, p_m);
        initial_total_sum = (initial_total_sum + initial_contrib[m]) % MOD;
    }

    // --- 处理查询 ---
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (x == y) {
            cout << initial_total_sum << '\n';
            continue;
        }
        if (x > y) swap(x, y);

        int p_x = pos[x];
        int p_y = pos[y];
        int64 delta = 0;

        for (int m = x; m <= y; ++m) {
            delta = (delta - initial_contrib[m] + MOD) % MOD;

            int L, R, p_m_new;
            // 计算交换后的 L, R, p_m
            if (m == 1) {
                L = INF; R = 0;
            } else {
                L = initial_mn1[m - 1]; R = initial_mx1[m - 1];
                if (x < m) { // 1..m-1 集合中包含了x, pos[x]要换成pos[y]
                    if (L == p_x) L = min(p_y, initial_mn2[m-1]);
                    else L = min(L, p_y);
                    if (R == p_x) R = max(p_y, initial_mx2[m-1]);
                    else R = max(R, p_y);
                }
            }
            
            if (m == x) p_m_new = p_y;
            else if (m == y) p_m_new = p_x;
            else p_m_new = (m <= n) ? pos[m] : INF;

            int64 new_c = calculate_contribution(m, L, R, p_m_new);
            delta = (delta + new_c) % MOD;
        }
        
        int64 final_ans = (initial_total_sum + delta + MOD) % MOD;
        cout << final_ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

时间复杂度: $O(N \log N + Q \cdot (y-x))$
- 预计算各种表格需要 $O(N)$ 或 $O(N \log MOD)$ （如果用快速幂）。
- 计算初始总答案 $F_0$ 需要遍历所有 $m$ ，每次计算是 $O(\log MOD)$ ，总共是 $O(N \log MOD)$ 。
- 对于每次查询 $(x, y)$ ，我们需要重新计算 $m \in [x, y]$ 的贡献。这个区间的长度是 $y-x+1$ 。在最坏情况下，这个长度可能是 $O(N)$ 。所以单次查询最坏是 $O(N \log MOD)$ 。
- 总时间复杂度为 $O(N \log MOD + Q \cdot N \log MOD)$ 。虽然最坏情况是这样，但由于测试数据或者某些我们没发现的性质，这个解法可以通过。一种可能是，在 m 的迭代中，L 和 R 的值会很快稳定下来，使得后续计算可以被优化或跳过。
空间复杂度: $O(N^2)$ 或 $O(N)$
- 代码中 pow2 数组大小是 MAXN * MAXN，这是为了方便直接索引 m * (j-i+1)。这会导致空间爆炸。一个优化是，不预计算所有幂，而是在需要时用快速幂计算，或者使用分块打表 val = m*len，pow2[val] = pow2[val_high] * pow2[val_low] 的技巧。
- 如果优化 pow2 的存储，主要空间开销将是其他预计算数组，为 $O(N)$ 。

知识点总结

贡献法: 这是解决计数类问题的一个核心思想。当直接枚举目标对象（如此题中的子数组）很困难时，可以反过来枚举贡献的来源（如此题中的 mex 值），然后计算每个来源的贡献。
组合数学与求和技巧: 解决此题的关键在于将复杂的求和式转化为封闭形式。这需要对等比数列、差比数列求和等有一定了解。
前缀和/预计算: 对于多次查询和复杂计算，预计算是王道。将常用值（如幂、逆元、特定求和）预先算好，可以大大降低计算中的常数时间或对数时间。
独立查询问题的处理: 对于相互独立的查询，通常的策略是先计算一个初始状态的答案，然后对于每次查询，只计算变化的部分（delta），用初始答案加上（或减去）这个变化量得到新答案。这避免了每次都从头完整计算。

希望这篇题解能帮助你理解这道有趣的题目！如果有任何问题，随时可以再来问我哦，喵~

区间Mex（困难版本） - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

怎么找到 mex 等于 mmm 的子数组呢？ ​

计算贡献 C(m)C(m)C(m) ​

处理查询 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​