CF2249A Rank Subsequence

有 $n$ 个元素排成一行，从左到右编号为 $1, 2, \ldots, n$。 你可以删除任意数量的元素（也可以一个不删）。删除后的剩余元素构成一个子序列，且保持原有的相对顺序。设该子序列的长度为 $m$。若原来下标为 $i$ 的元素成为子序列中的第 $j$ 个元素（$1\le j\le m$），则定义： - 它的左秩为 $j$， - 它的右秩为 $m-j+1$。 对于每个元素，给定两个整数区间 $[l_i, r_i]$ 和 $[u_i, v_i]$。若第 $i$ 个元素在长度为 $m$ 的子序列中处于第 $j$ 个位置，则当且仅当同时满足： - 它的左秩不属于区间 $[l_i, r_i]$（即 $j \notin [l_i, r_i]$）； - 它的右秩不属于区间 $[u_i, v_i]$（即 $m-j+1 \notin [u_i, v_i]$）。 第 $i$ 个元素才在该子序列中合法。 当子序列中的每个元素在该子序列中都合法时，称该子序列为合法子序列。 请你求出合法子序列的最大可能长度。若无法构成合法子序列，则答案为 $0$。

每组测试数据包含若干个测试用例。第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例数量。 接下来是每个测试用例的描述： 每个测试用例的第一行为一个整数 $n$（$1 \le n \le 5000$），表示元素数量。 接下来的 $n$ 行，每行为四个整数 $l_i, r_i, u_i, v_i$（$1\le i\le n$，$1\le l_i\le r_i\le n$，$1\le u_i\le v_i\le n$）。 保证所有测试用例中 $n$ 的总和不超过 $5000$。

每个测试用例输出一行，一个整数，表示合法子序列的最大长度。

在第一个测试用例中，唯一的元素无法构成长度为 $1$ 的合法子序列，因此答案为 $0$。 在第二个测试用例中，所有 $4$ 个元素均可保留。它们的左右秩分别为 $(1, 4)$、$(2, 3)$、$(3, 2)$ 和 $(4, 1)$，均合法。 在第三个测试用例中，一种最优方案是保留原始下标为 $2$、$3$ 和 $5$ 的元素。 在第四个测试用例中，保留两个元素可以构成长度为 $2$ 的合法子序列。注意不可能构成长度为 $1$ 的合法子序列。 在第五个测试用例中，一种最优方案是保留原始下标为 $3$、$4$ 和 $5$ 的元素。 由 ChatGPT 5 翻译