[PAT顶级1027] Larry和逆序对–区间dp
题目描述
给定一个长度为 $n$ 的数组(保证是一个 $1\sim n$ 的排列),然后输出 $n(n+1)/2$ 个整数,表示将该数组的子区间 $[1,1], [1,2],…,[1,n],[2,2],[2,3],…,[2,n],....,[n,n]$ 翻转之后,整个数组的逆序对是多少(每次翻转操作互相独立,仅在原数组上进行操作)。保证 $n\le 1000$ 。
样例
样例输入 #1
3
2 1 3
样例输出 #1
1 0 2 1 2 1
样例解释
The original array is { 2, 1, 3 }.
Reversing subarray [1..1] makes { 2, 1, 3 } has 1 inversion.
Reversing subarray [1..2] makes { 1, 2, 3 } has 0 inversion.
Reversing subarray [1..3] makes { 3, 1, 2 } has 2 inversions.
Reversing subarray [2..2] makes { 2, 1, 3 } has 1 inversion.
Reversing subarray [2..3] makes { 2, 3, 1 } has 2 inversions.
Reversing subarray [3..3] makes { 2, 1, 3 } has 1 inversion.
思路
首先那个“满足 $1\sim n$ 的排列”的条件根本不必要。
我们先考虑在原数组区间dp,设 $dp[i][j]$ 为子数组 $[i,j]$ 的逆序对个数,那么可以得到状态转移方程:
$dp[l][r]=dp[l+1][r]+dp[l][r-1]-dp[l+1][r-1]+(a[l]>a[r])\quad (1\le l\le r\le n)$
初始方程有 $dp[i][i]=0\quad(1\le i\le n)$ ,所以我们外层按照长度从 $1$ 到 $n$ ,内层区间右端点从 $len$ 到 $n$ 进行dp就完事了,复杂度是 $O(n^2)$ 。
然后考虑翻转一个子数组之后逆序对的变化。假设我们翻转的是 $[l,r]$ ,那么 $[1,l-1]$ 和 $[r+1,n]$ 这两个子区间逆序对个数显然不变,然后这两个子区间共同带来的逆序对个数贡献也不会变(也就是一个数从前面选,一个数从后面选,两者是否构成逆序对)。唯一变化的只有 $[l, r]$ 这里。那么我们将数组整个翻转,每次的答案为——原数组总逆序对个数-查询子区间逆序对个数+该子区间翻转之后的逆序对个数。
dp两次复杂度 $O(n^2)$ ,$O(n^2)$ 次查询每次都是 $O(1)$,总复杂度 $O(n^2)$ 。
int n, a[N], rev[N];
int dp[N][N], rdp[N][N];
void build_dp()
{
for (int len = 1; len <= n; ++len)
for (int l = 1, r = l + len - 1; r <= n; ++l, ++r)
{
dp[l][r] = dp[l + 1][r] + dp[l][r - 1] - dp[l + 1][r - 1] + (a[l] > a[r]);
rdp[l][r] = rdp[l + 1][r] + rdp[l][r - 1] - rdp[l + 1][r - 1] + (rev[l] > rev[r]);
}
}
int query(int l, int r) { return dp[1][n] - dp[l][r] + rdp[n - r + 1][n - l + 1]; }
int main()
{
n = rd();
for (int i = 1; i <= n; ++i)
rev[n - i + 1] = a[i] = rd();
build_dp();
int lim = (n * (n + 1)) >> 1, cnt = 1;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j, putchar((i == n && j > n) ? '\0' : ' '))
wr(query(i, j));
}