D2.逆序图染色（困难版本） 题解

一、与简单版本的区别

• 困难版本：$n \leq 2000$，$\sum n \leq 2000$。
• 简单版本的 $O(n^3)$ DP 不再可行，需要优化至 $O(n^2 \log n)$ 或 $O(n^2)$。

二、核心观察

回顾 D1 的 DP 状态：$ways[m][mp]$ 表示当前子序列中最大值为 $m$、被更大元素领先过的最大值为 $mp$ 的方案数。

转移方程：

• 不选当前元素：$ways[m][mp]$ 自动继承。
• 选当前元素 $x$：
  • 若 $x > m$：$ways[x][mp] \mathrel{+}= ways[m][mp]$（对所有 $m < x$）
  • 若 $mp < x < m$：$ways[m][x] \mathrel{+}= ways[m][mp]$（对所有 $mp < x$）

注意到每次迭代只有 $O(n)$ 个位置被更新（第 $x$ 行和第 $x$ 列），而非整个矩阵。

三、优化思路

3.1 消除时间维度

由于"不选"操作自动继承上一层的值，我们可以直接在原地更新矩阵，无需存储 $i$ 维度。

设当前矩阵为 $ways[m][mp]$，对每个新元素 $x = a_i$：

• 更新第 $x$ 行：$ways[x][mp] \mathrel{+}= \sum_{m'=0}^{x-1} ways[m'][mp]$（$x$ 成为新的最大值）
• 更新第 $x$ 列：$ways[m][x] \mathrel{+}= \sum_{mp'=0}^{x-1} ways[m][mp']$（$x$ 成为新的被领先最大值，仅对 $m > x$）

3.2 数据结构加速

上述转移需要对每一行和每一列求前缀和。可以使用**树状数组（Fenwick Tree）**维护：

• 对每一行 $m$ 维护一个树状数组，存储该行所有 $mp$ 的方案数。
• 对每一列 $mp$ 维护一个树状数组，存储该列所有 $m$ 的方案数。

更新：

• $ways[x][mp]$ 增加 $val$ → 在行 $x$ 的树状数组位置 $mp$ 加 $val$，同时在列 $mp$ 的树状数组位置 $x$ 加 $val$。

查询：

• $\sum_{m'=0}^{x-1} ways[m'][mp]$ → 查询列 $mp$ 的树状数组前缀和到 $x-1$。
• $\sum_{mp'=0}^{x-1} ways[m][mp']$ → 查询行 $m$ 的树状数组前缀和到 $x-1$。

四、算法流程

1. 离散化：将原序列 $b$ 压缩为排列 $a$（保留偏序关系）。
2. 初始化：$ways[0][0] = 1$，在行 $0$ 和列 $0$ 的树状数组中各加 $1$。
3. 对于每个 $i = 1$ 到 $n$：
   • 令 $x = a_i$。
   • 对于所有 $j > x$（$j$ 作为 $m$）：
     • $val = \text{query\_行}_j(x-1)$（$\sum_{mp'=0}^{x-1} ways[j][mp']$）
     • 若 $val > 0$，记录更新 $(j, x)$ 增加 $val$。
   • 对于所有 $q < x$（$q$ 作为 $mp$）：
     • $val = \text{query\_列}_q(x-1)$（$\sum_{m'=0}^{x-1} ways[m'][q]$）
     • 若 $val > 0$，记录更新 $(x, q)$ 增加 $val$。
   • 批量执行所有记录的更新（更新行和列树状数组）。
4. 答案：$\sum_{m=0}^n \sum_{mp=0}^n ways[m][mp] = \sum_{m=0}^n \text{query\_行}_m(n)$。

五、代码实现（C++）

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

const int MOD = 1e9 + 7;
const int NMAX = 2005;

int n;
int a[NMAX], b[NMAX];
int bit_lin[NMAX][NMAX], bit_col[NMAX][NMAX];

void addSelf(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

void update_lin(int lin, int pos, int val) {
    pos++;
    for (int i = pos; i <= n + 1; i += (i & -i))
        addSelf(bit_lin[lin][i], val);
}

void update_col(int col, int pos, int val) {
    pos++;
    for (int i = pos; i <= n + 1; i += (i & -i))
        addSelf(bit_col[col][i], val);
}

int query_lin(int lin, int pos) {
    pos++;
    int res = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        addSelf(res, bit_lin[lin][i]);
    return res;
}

int query_col(int col, int pos) {
    pos++;
    int res = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        addSelf(res, bit_col[col][i]);
    return res;
}

void solve() {
    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]++;
    }
    
    // 清空树状数组
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= n + 1; j++)
            bit_lin[i][j] = bit_col[i][j] = 0;
    
    // 初始状态：空子序列
    update_lin(0, 0, 1);
    update_col(0, 0, 1);
    
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        vector<tuple<int, int, int>> buffs;  // (val, lin, col)
        
        // 更新第 x 列：ways[m][x] += sum_{mp' < x} ways[m][mp']
        for (int j = x + 1; j <= n; j++) {
            int val = query_lin(j, x - 1);
            if (val) buffs.push_back({val, j, x});
        }
        
        // 更新第 x 行：ways[x][mp] += sum_{m' < x} ways[m'][mp]
        for (int q = 0; q < x; q++) {
            int val = query_col(q, x - 1);
            if (val) buffs.push_back({val, x, q});
        }
        
        // 批量更新
        for (auto [val, lin, col] : buffs) {
            update_lin(lin, col, val);
            update_col(col, lin, val);
        }
    }
    
    // 求和
    int ans = 0;
    for (int lin = 0; lin <= n; lin++)
        addSelf(ans, query_lin(lin, n));
    
    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)$（可优化至 $O(n \log n)$，但 $n \leq 2000$ 不需要）。
• DP 转移：每轮枚举 $O(n)$ 个位置，每次查询/更新树状数组 $O(\log n)$。
• 总复杂度：$O(n^2 \log n)$，对于 $n \leq 2000$ 完全可行。
• 空间复杂度：$O(n^2)$（两个二维树状数组）。