D1.逆序图染色（简单版本） 题解

---

一、题意理解

• 给定序列 $a_1, a_2, \dots, a_n$。
• 一个序列是好的，如果可以将每个位置染红或蓝，使得对于任意逆序对 $(i, j)$（$i < j$ 且 $a_i > a_j$），两个位置颜色不同。
• 求好子序列的数量（包括空子序列），对 $10^9 + 7$ 取模。
• 简单版本：$n \leq 300$，$\sum n \leq 300$。

---

二、图论转化

2.1 冲突图

将序列看作图的顶点，对于每一对 $i < j$ 满足 $a_i > a_j$，在 $i$ 和 $j$ 之间连一条边。这样得到的图称为逆序图。

"好的"序列意味着该图是二分图（可 $2$-染色）。

2.2 二分图判定定理

定理：一个图是二分图，当且仅当它不包含奇环。

对于逆序图，有如下更强的结论：

逆序图是 $k$-可染色的，当且仅当序列的**最长下降子序列（LDS）**的长度不超过 $k$。

证明：

• 若 LDS 长度 $> k$，则这些元素两两之间都是逆序（全相连），构成大小为 $> k$ 的团，不可 $k$-染色。
• 若 LDS 长度 $\leq k$，可令每个元素 $i$ 的颜色为"以 $i$ 开头的最长下降子序列的长度"。这样，若 $i < j$ 且有边（$a_i > a_j$），则以 $i$ 开头的 LDS 至少比以 $j$ 开头的长 $1$，因此两者颜色不同。

本题特例：好序列 $\iff$ LDS 长度 $\leq 2$。

---

三、动态规划设计

3.1 在线判定 LDS $\leq 2$

对于一个序列，如何判断其 LDS 是否 $\leq 2$？

扫描序列，维护两个值：

• $m$：当前已见的最大元素值。
• $mp$（maxpreceeded）：当前已见的、被更大元素领先过的最大元素值。即存在某个更大的元素出现在它之前。

判定条件：LDS $\leq 2$，当且仅当对于每个新元素，它不会小于当前的 $mp$。

因为如果新元素 $< mp$，则存在三个元素形成下降三元组：大元素 $\to$ 中元素 $(mp)$ $\to$ 新元素，LDS 长度将达到 $3$。

3.2 DP 状态

设 $dp[i][m][mp]$ 表示考虑前 $i$ 个元素，所选子序列中：

• $m$：已选的最大元素值。
• $mp$：已选的、被更大元素领先过的最大元素值。

若 $m$ 或 $mp$ 不存在，用 $0$ 表示。

初始状态：$dp[0][0][0] = 1$（空子序列）。

3.3 状态转移

对于第 $i$ 个元素 $a_i$，设其在原序列中的"压缩值"为 $x$（离散化后的排名）。

不选 $a_i$：

$$dp[i][m][mp] \mathrel{+}= dp[i-1][m][mp]$$

选 $a_i$（从 $dp[i-1][m][mp]$ 转移）：

• 情况 1：$x \geq m$（$a_i$ 成为新的最大值）

  $$dp[i][x][mp] \mathrel{+}= dp[i-1][m][mp]$$

  $mp$ 不变，因为 $a_i$ 是新的最大值，没有被其他元素领先。

• 情况 2：$mp \leq x < m$（$a_i$ 介于 $mp$ 和 $m$ 之间）

  $$dp[i][m][x] \mathrel{+}= dp[i-1][m][mp]$$

  $m$ 不变（已有更大值），$a_i$ 成为新的"被领先过的最大值"。

• 情况 3：$x < mp$（$a_i$ 小于当前 $mp$） 此转移无效，因为会形成下降三元组，LDS 长度变为 $3$。

---

四、值域压缩

由于 DP 状态中的 $m$ 和 $mp$ 只取决于值的相对大小，需要将原序列 $b$ 离散化为 $1$ 到 $n$ 的排列。

压缩方法：对于每个位置 $i$，计算 $a_i$ 等于 $1$ 加上数组中比 $b_i$ 小的元素个数（包含重复元素需特殊处理）。

标程中的压缩公式：

$$a_i = 1 + |\{j < i : b_j \leq b_i\}| + |\{j > i : b_j < b_i\}| $$

这使得 $a_i \in [1, n]$ 且保留原序列的所有偏序关系。

---

五、算法流程

1. 读入 $n$ 和序列 $b$。
2. 将 $b$ 压缩为 $1$ 到 $n$ 的排列 $a$（保留元素间的 $\leq$ 和 $<$ 关系）。
3. 初始化滚动数组 $dp[0/1][n+1][n+1] = 0$，$dp[0][0][0] = 1$。
4. 对于每个 $i = 1$ 到 $n$：
   • 先将上一层的 DP 值复制到当前层（不选的情况）。
   • 遍历所有状态 $(m, mp)$，若上一层的 $dp[m][mp] > 0$：
     • 若 $m > x$ 且 $x > mp$：更新 $dp[cr][m][x]$。
     • 若 $x > m$：更新 $dp[cr][x][mp]$。
5. 最终答案 = $\sum_{m=0}^n \sum_{mp=0}^n dp[n][m][mp]$。

---

六、标程解析

void testcase() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> b[i];
    
    // 离散化
    for (int i = 1; i <= n; i++) {
        a[i] = 1;
        for (int j = 1; j < i; j++)
            if (b[j] <= b[i]) a[i]++;
        for (int j = i + 1; j <= n; j++)
            if (b[j] < b[i]) a[i]++;
    }
    
    // 滚动数组
    int cr = 0;
    dp[0][0][0] = 1;
    
    for (int i = 1; i <= n; i++) {
        cr ^= 1;
        int x = a[i];
        
        // 复制：不选 a[i]
        for (int j = 0; j <= n; j++)
            for (int q = 0; q <= n; q++)
                dp[cr][j][q] = dp[cr ^ 1][j][q];
        
        // 选 a[i] 的转移
        for (int j = 0; j <= n; j++) {
            for (int q = 0; q <= j; q++) {
                if (dp[cr ^ 1][j][q] == 0) continue;
                
                if (j > x && x > q)          // mp < a[i] < m
                    addSelf(dp[cr][j][x], dp[cr ^ 1][j][q]);
                else if (x > j)              // a[i] >= m
                    addSelf(dp[cr][x][q], dp[cr ^ 1][j][q]);
            }
        }
    }
    
    int ans = 0;
    for (int j = 0; j <= n; j++)
        for (int q = 0; q <= n; q++)
            addSelf(ans, dp[cr][j][q]);
    cout << ans << '\n';
}

步骤：

1. 压缩序列得到 $a$。
2. DP 中使用滚动数组优化空间。
3. 对于每个元素 $x = a_i$，枚举状态 $(j, q) = (m, mp)$，按两种情况转移。
4. 最终求和所有 DP 状态。

---

七、代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

void add(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void solve() {
    int n;
    cin >> n;
    vector<int> b(n + 1), a(n + 1);
    for (int i = 1; i <= n; i++) cin >> b[i];
    
    // 离散化
    for (int i = 1; i <= n; i++) {
        a[i] = 1;
        for (int j = 1; j < i; j++)
            if (b[j] <= b[i]) a[i]++;
        for (int j = i + 1; j <= n; j++)
            if (b[j] < b[i]) a[i]++;
    }
    
    // dp[cr][m][mp]
    vector<vector<vector<int>>> dp(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
    dp[0][0][0] = 1;
    int cr = 0;
    
    for (int i = 1; i <= n; i++) {
        cr ^= 1;
        int x = a[i];
        
        // 不选 a[i]：复制上一层
        for (int j = 0; j <= n; j++)
            for (int q = 0; q <= n; q++)
                dp[cr][j][q] = dp[cr ^ 1][j][q];
        
        // 选 a[i]
        for (int j = 0; j <= n; j++) {
            for (int q = 0; q <= j; q++) {
                int val = dp[cr ^ 1][j][q];
                if (val == 0) continue;
                
                if (j > x && x > q)       // mp < a[i] < m
                    add(dp[cr][j][x], val);
                else if (x > j)           // a[i] >= m
                    add(dp[cr][x][q], val);
            }
        }
    }
    
    int ans = 0;
    for (int j = 0; j <= n; j++)
        for (int q = 0; q <= n; q++)
            add(ans, dp[cr][j][q]);
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) solve();
    
    return 0;
}

---

八、复杂度分析

• 状态数：$O(n^2)$（$m, mp$ 各 $n+1$ 种可能）。
• 每个元素 $O(n^2)$ 枚举状态转移。
• 总复杂度：$O(n^3)$，$n \leq 300$，完全可行。
• 空间复杂度：$O(n^2)$（滚动数组）。