本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
Problem - D1 - Codeforces
题目类型
#DP #Dilworth
解题思路
条件分析：
如果子序列里出现了逆序对，则这两个下标必须染成不同颜色。换而言之，子序列可以被拆成两个非递减子序列（红色一份，蓝色一份）。
一个子序列是 good ⇔ 它可以被分成两个单调递增（不降）的 subsequence，是一个经典结论（Dilworth 定理相关）。
转移方程：
定义两个子序列结尾元素为 l 和 r，通过枚举数组元素 x，考虑可以加入的子序列，累加合法方案更新 DP。
示例代码
python
def helltractor():
for _ in range(II()):
n = II()
a = LII()
f = [[0] * (n + 1) for _ in range(n + 1)]
f[0][0] = 1
for x in a:
for l in range(x + 1, n + 1):
for r in range(x, -1, -1):
f[l][x] = (f[l][x] + f[l][r]) % MOD1
for r in range(x + 1):
for l in range(x, r - 1, -1):
f[x][r] = (f[x][r] + f[l][r]) % MOD1
print(sum(sum(row) for row in f) % MOD1)Problem - D2 - Codeforces
题目类型
#DP #Dilworth #树状数组
解题思路
思路同 D1，由于数据范围变大，需要采用树状数组、线段树等优化区间和。由于变化只发生在单行或单列上，可以采用一维树状数组进一步优化。
示例代码
python
def helltractor():
for _ in range(II()):
n = II()
a = LII()
tree = RangeAddRangeSum2D(n + 2, n + 2)
tree.range_add(1, 1, 1, 1, 1)
for x in a:
for l in range(x + 1, n + 1):
res = tree.range_query(l, 1, l, x)
tree.range_add(l, x, l, x, res % MOD1)
for r in range(1, x + 1):
res = tree.range_query(r, r, x, r)
tree.range_add(x, r, x, r, res % MOD1)
print(tree.range_query(1, 1, n + 1, n + 1) % MOD1)python
def helltractor():
for _ in range(II()):
n = II()
a = LII()
rows = [[0] * (n + 2) for _ in range(n + 1)]
cols = [[0] * (n + 2) for _ in range(n + 1)]
def update(tree, idx, val):
while idx <= n + 1:
tree[idx] = (tree[idx] + val) % MOD1
idx += idx & -idx
def query(tree, idx):
res = 0
while idx:
res = (tree[idx] + res) % MOD1
idx -= idx & -idx
return res % MOD1
def update2(idx1, idx2, val):
update(rows[idx1], idx2, val)
update(cols[idx2], idx1, val)
update2(1, 1, 1)
for x in a:
for l in range(x + 1, n + 1):
update2(x, l, query(cols[l], x))
for r in range(1, x + 1):
update2(r, x, query(rows[r], x))
print(sum(query(rows[i], n + 1) for i in range(1, n + 1)) % MOD1)py
class FenwickTree2D:
def __init__(self, m: int, n: int) -> None:
self.m = m # row
self.n = n # col
self.t1 = [[0] * (n + 1) for _ in range(m + 1)]
self.t2 = [[0] * (n + 1) for _ in range(m + 1)]
self.t3 = [[0] * (n + 1) for _ in range(m + 1)]
self.t4 = [[0] * (n + 1) for _ in range(m + 1)]
return
def _add(self, x: int, y: int, val: int) -> None:
# index start from 1 and single point add val and val cam be any integer
i = x
while i <= self.m:
j = y
while j <= self.n:
self.t1[i][j] += val
self.t2[i][j] += val * x
self.t3[i][j] += val * y
self.t4[i][j] += val * x * y
j += j & -j
i += i & -i
return
def range_add(self, x1: int, y1: int, x2: int, y2: int, val: int) -> None:
# index start from 1 and left up corner is (x1, y1) and right down corner is (x2, y2) and val can be any integer
self._add(x1, y1, val)
self._add(x1, y2 + 1, -val)
self._add(x2 + 1, y1, -val)
self._add(x2 + 1, y2 + 1, val)
return
def _query(self, x: int, y: int) -> int:
# index start from 1 and query the sum(sum(g[:y]) for g in grid[:x]) which is 0-index
assert 0 <= x <= self.m and 0 <= y <= self.n
res = 0
i = x
while i:
j = y
while j:
res += (x + 1) * (y + 1) * self.t1[i][j] - (y + 1) * self.t2[i][j] - (x + 1) * self.t3[i][j] + \
self.t4[i][j]
j -= j & -j
i -= i & -i
return res
def range_query(self, x1: int, y1: int, x2: int, y2: int) -> int:
# index start from 1 and left up corner is (x1, y1) and right down corner is (x2, y2)
return self._query(x2, y2) - self._query(x2, y1 - 1) - self._query(x1 - 1, y2) + self._query(x1 - 1, y1 - 1)