题解：CF2143D2 Inversion Graph Coloring (Hard Version)

· · 题解

题面转化

给定一个序列，问子序列中最长下降子序列长度小于等于 2 的子序列，有多少个。

solution

首先，我们发现这道题并不关心子序列的最长下降子序列的长度，只关心子序列的最长下降子序列是否大于 2。所以我们的动规状态只需要记录有可能使最长上升子序列的长度大于 2 的值。具体的，对于 n \le 100 的情况，我们可以设置一个状态 f_{i, j, k} 代表当前扫到第 i 个数，前面的最大值为第 j 个数时，最大的作为下降子序列二号位的数为第 k 个数（即第 k 个数前有比它大的数，且没有更大的数满足同样的要求）的状态数。

对于这个状态我们可以写出转移方程。首先，只有 a_k \le a_i 时，状态才合法。此时，若 a_j \le a_i 则 f_{i, i, k} = f_{i, i, k} + f_{i', j, k}。若 a_j > a_i，则 f_{i, j, i} = f_{i, j, i} + f_{i', j, k}。

注意到，第一维的 i 实则没用，所以我们可以改写一下状态 f_{i, j} 表示最大的数为 i，最大的作为下降子序列二号位的数为 k（即 k 前有比它大的数，且没有更大的数满足同样的要求）的状态数。

假设我们枚举到第 k 个数。
这时我们又注意到，对于 i \le a_k 我们并不关心 i 的大小，只关心 j 的大小，所以我们可以枚举 j，用一个数据结构快速维护一下 f_{a_k, j} = f_{a_k, j} + \sum_{i \le a_k} f_{i, j}。
这时我们又注意到，对于 i > a_k 我们并不关心 j 的大小，我们只关心 i 的大小，这时我们可以枚举 i，用一个数据结构快速维护一下 f_{i, a_k} = f_{i, a_k} + \sum_{i > a_k} f_{i, j}。

然后我们就做完了，时间复杂度 O(n ^ 2 \log n) 。

code

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define N 2005
int n, a[N], tree1[N][N], tree2[N][N], ans;
inline void update1(int x, int y, int z) {
    while(x <= n) 
        tree1[y][x] += z, 
        tree1[y][x] %= mod, 
        x += x & -x;
}
inline int query1(int x, int y) {
    int ret = 0;
    while(x) 
        ret += tree1[y][x], 
        ret %= mod, x -= x & -x;
    return ret;
}
inline void update2(int x, int y, int z) {
    while(x <= n) 
        tree2[x][y] += z, 
        tree2[x][y] %= mod, 
        x += x & -x;
}
inline int query2(int x, int y) {
    int ret = 0;
    while(x) 
        ret += tree2[x][y], 
        ret %= mod, x -= x & -x;
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        ans = 0;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = n; i; --i) 
            for(int j = n; j; --j) 
                tree1[i][j] = tree2[i][j] = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = a[i]; j; --j) {
                int up = query2(a[i], j);
                ans += up, ans %= mod;
                update1(j, a[i], up), update2(a[i], j, up);
            }
            for(int j = n; j > a[i]; --j) {
                int up = query1(a[i], j);
                ans += up, ans %= mod;
                update1(a[i], j, up), update2(j, a[i], up);
            }
            ++ans, ans %= mod;
            update1(1, a[i], 1), update2(a[i], 1, 1);
        }
        printf("%d\n", ans + 1);
    }
    return 0;
}