Mysterious Array题解

一、问题分析

我们需要统计所有满足 $Q$ 个区间最小值查询的 $1$ 到 $N$ 排列的数量。每个查询给出区间 $[a,b]$ 的最小值为 $x$。

二、算法思路

1. 关键观察

对于值为 $i$ 的元素：

• 它必须出现在所有以 $i$ 为最小值的区间内
• 因此可以确定 $i$ 出现的可能位置范围 $[l_i, r_i]$
• 同时，每个位置 $p$ 有一个下界 $mn_p$，表示该位置的值至少是多少

2. 预处理位置约束

for (int i = 1; i <= n; i++) {
    l[i] = 1;
    r[i] = n;
}

for (int i = 1; i <= Q; i++) {
    auto [L, R, v] = q[i];
    l[v] = max(l[v], L);    // 值v必须出现在区间[L,R]内
    r[v] = min(r[v], R);
    tag[v] = 1;             // 标记值v被查询提到过
    seg.update(L, R, 1, n, 1, v);  // 更新区间最小值下界
}

作用：

• l[i], r[i] 记录值 $i$ 可以出现的范围
• tag[i] 标记值 $i$ 是否作为某个查询的最小值出现

3. 计算每个位置的最小值下界

使用线段树维护区间赋值（取最大值），查询每个位置的最小值下界：

struct SegmentTree {
    int tree[N << 2];
    void update(int l, int r, int s, int t, int p, int v) {
        if (l <= s && t <= r) {
            tree[p] = v;  // 区间赋值（实际是取max）
            return;
        }
        // ... 递归更新左右子树
    }
    int query(int l, int r, int x, int p) {
        // 查询时带上路径上的所有标记
        if (x <= m) return max(tree[p], query(l, m, x, p << 1));
        else return max(tree[p], query(m + 1, r, x, p << 1 | 1));
    }
};

for (int i = 1; i <= n; i++) 
    mn[i] = seg.query(1, n, i, 1);  // 位置i的值至少为mn[i]

4. 统计合法排列数量

按值从小到大考虑分配位置：

iota(pos + 1, pos + n + 1, 1);
sort(pos + 1, pos + n + 1, [&](int a, int b) {
    if (mn[a] != mn[b]) return mn[a] < mn[b];
    return a < b;
});

ll ans = 1;
int j = 1, idx = 1;

for (int i = 1; i <= n; i++) {
    // 找到所有最小值约束<=i的位置
    while (j <= n && mn[pos[j]] <= i) j++;
    j--;
    
    // 统计在值i的允许范围内且满足约束的位置数量
    int cnt = 0;
    for (int k = idx; k <= j; k++) 
        cnt += (pos[k] >= l[i] && pos[k] <= r[i]);
    
    if (!tag[i]) 
        ans = ans * (j - i + 1) % mod;  // 值i未被查询提到，可在剩余位置任选
    else 
        ans = ans * cnt % mod;          // 值i必须出现在特定范围内
    
    idx = j;
}

计数原理：

• 对于值 $i$，我们考虑所有最小值约束 $\leq i$ 的位置
• 如果值 $i$ 被某个查询提到过 (tag[i] = 1)，它只能出现在 $[l_i, r_i]$ 内且满足约束的位置
• 如果值 $i$ 没被提到过，它可以在剩余的任何位置出现

三、复杂度分析

• 预处理：$O(Q \log N)$（线段树更新）
• 位置排序：$O(N \log N)$
• 统计答案：$O(N^2)$ 最坏（内层循环），但实际运行较快

该算法通过结合位置约束和值约束，高效地统计了满足所有区间最小值查询的排列数量。