C. Monopati

时间限制：每个测试 2 秒
内存限制：每个测试 256 MB

问题描述

给定一个 2 行 $n$ 列的网格 $a$，其中每个单元格的值在 $1$ 到 $2n$ 之间。

定义 $f(l,r)$，其中 $1 \leq l \leq r \leq 2n$，表示一个 2 行 $n$ 列的二进制网格 $b$，使得 $b_{i,j} = 1$ 当且仅当 $l \leq a_{i,j} \leq r$。注意单元格 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的单元格。

计算满足 $1 \leq l \leq r \leq 2n$ 的整数对 $(l,r)$ 的数量，使得在 $f(l,r)$ 中存在一条从单元格 $(1,1)$ 到 $(2,n)$ 的右下路径，该路径由值为 1 的相邻单元格组成。

$*$ 当且仅当网格的每个单元格的值都是 0 或 1 时，该网格被认为是二进制网格。

$†$ 相邻单元格的右下路径是一个单元格序列，使得序列中的每个单元格与序列中的前一个单元格共享其顶部或左侧的一条边。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 10^4$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$ ($2 \leq n \leq 2 \cdot 10^5$) —— 网格中的列数。

第二行包含恰好 $n$ 个整数 $a_{1,1}, a_{1,2}, \dots, a_{1,n}$ ($1 \leq a_{1,i} \leq 2n$) —— 网格第一行单元格的值。

第三行包含恰好 $n$ 个整数 $a_{2,1}, a_{2,2}, \dots, a_{2,n}$ ($1 \leq a_{2,i} \leq 2n$) —— 网格第二行单元格的值。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，在单独一行输出一个整数，表示满足条件的整数对 $(l,r)$ 的数量。

样例输入

5
2
1 3
3 1
3
1 2 3
3 2 1
4
1 5 5 5
5 3 1 2
4
8 8 8 8
8 8 8 8
6
6 6 5 7 9 12
1 4 2 8 5 6

样例输出

2
5
4
8
25

样例说明

考虑第一个样例。

网格 $f(1,1)$ 和 $f(1,2)$ 如下所示：

10
01

不存在从左上角单元格到右下角单元格的 1 的路径，因此不计算 $(1,1)$ 和 $(1,2)$ 对。

网格 $f(1,3)$ 和 $f(1,4)$ 如下所示：

11
11

由于存在从 $(1,1)$ 到 $(2,2)$ 的有效路径，因此计算 $(1,3)$ 和 $(1,4)$ 对。

网格 $f(2,2)$ 和 $f(4,4)$ 如下：

00
00

网格 $f(2,3)$、$f(2,4)$、$f(3,3)$ 和 $f(3,4)$ 如下所示：

01
10

因此不计算 $(2,3)$、$(2,4)$、$(3,3)$ 和 $(3,4)$ 对。

仅计算 $(1,3)$ 和 $(1,4)$ 对，因此答案是 $2$。

赛时WA 2代码

// Problem: CF 2163 C
// Contest: Codeforces - Codeforces Round 1063 (Div. 2)
// URL: https://codeforces.com/contest/2163/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e9+7,INF=0x3f3f3f3f;


void solve() {
    int n;
    cin>>n;
    vector<int> premax(n+3,0),premin(n+3,INF);
    vector<int> sufmax(n+3,0),sufmin(n+3,INF);
    vector<int> a(n+3),b(n+3);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        premax[i]=max(a[i],premax[i-1]);
        premin[i]=min(a[i],premin[i-1]);
    }
    for(int i=n;i>=1;i--){
        sufmax[i]=max(b[i],sufmax[i+1]);
        sufmin[i]=min(b[i],sufmin[i+1]);
    }

    int l=0,r=2*n;
    for(int i=1;i<=n;i++){
        int mi=min(premin[i],sufmin[i]);
        int mx=max(premax[i],sufmax[i]);
        l=max(l,mi),r=min(r,mx);
    }
   // printf("%d %d\n",l,r);
    printf("%lld\n",l*(n*2-r+1));

    return;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

抄哥哥AC 代码

// Problem: CF 2163 C
// Contest: Codeforces - Codeforces Round 1063 (Div. 2)
// URL: https://codeforces.com/contest/2163/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e9+7,INF=0x3f3f3f3f;


void solve() {
    int n;
    cin>>n;
    vector<int> premax(n+3,0),premin(n+3,INF);
    vector<int> sufmax(n+3,0),sufmin(n+3,INF);
    vector<int> a(n+3),b(n+3);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        premax[i]=max(a[i],premax[i-1]);
        premin[i]=min(a[i],premin[i-1]);
    }
    for(int i=n;i>=1;i--){
        sufmax[i]=max(b[i],sufmax[i+1]);
        sufmin[i]=min(b[i],sufmin[i+1]);
    }

   vector<int> f(n*2+3,n*2+3);
   for(int i=1;i<=n;i++){
        int L=min(premin[i],sufmin[i]);
        int R=max(premax[i],sufmax[i]);
        f[L]=min(R,f[L]);//注意这里是L
   }
    for(int i=2*n;i>=0;i--){
        f[i]=min(f[i],f[i+1]);
    }
    LL ans=0;
    for(int i=2*n;i>=1;i--){
        ans+=max((2*n-f[i]+1),0LL);
    }
    printf("%lld\n",ans);
    return;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

jiangly 代码

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;

void solve() {
    int n;
    std::cin >> n;

    std::vector a(2, std::vector<int>(n));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> a[i][j];
            a[i][j]--;
        }
    }

    auto pmin = a[0], pmax = a[0], smin = a[1], smax = a[1];
    for (int i = 1; i < n; i++) {
        pmin[i] = std::min(pmin[i - 1], pmin[i]);
        pmax[i] = std::max(pmax[i - 1], pmax[i]);
    }
    for (int i = n - 2; i >= 0; i--) {
        smin[i] = std::min(smin[i + 1], smin[i]);
        smax[i] = std::max(smax[i + 1], smax[i]);
    }

    std::vector<int> f(2 * n, 2 * n);

    for (int i = 0; i < n; i++) {
        int L = std::min(pmin[i], smin[i]);
        int R = std::max(pmax[i], smax[i]);
        f[L] = std::min(f[L], R);
    }
    for (int i = 2 * n - 2; i >= 0; i--) {
        f[i] = std::min(f[i], f[i + 1]);
    }
    i64 ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        ans += 2 * n - f[i];
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

AI 对于jiangly 思路以及我的代码分析

你好！我们来分析这道题。

你这道题的 WA2 和 jiangly 的 AC 代码，思路差异非常大。你的代码尝试寻找一个“通用”的 $l$ 和 $r$，而 jiangly 的代码则在计算 $n$ 种可能路径的“并集”。

这道题的核心是如何正确地对“至少存在一个”这种条件进行计数。你的 WA 表明你可能在计算“对于所有都成立”的“交集”，这是一个根本性的误解。

让我们一步步拆解 jiangly 的正确思路。

步骤 1：分析路径 (Path)

我们首先要搞清楚“从 $(1,1)$ 到 $(2,n)$ 的右下路径”长什么样。

在一个 $2 \times n$ 的网格里，从 $(1,1)$ 出发，你只能向右或向下。要想到达 $(2,n)$，你的路径_必须_在某一列 $k$（$1 \le k \le n$）从第一行“掉到”第二行。

这个路径看起来就像：

1. 先在第一行，从 $(1,1)$ 走到 $(1,k)$。

2. 然后从 $(1,k)$ 掉到 $(2,k)$。

3. 最后在第二行，从 $(2,k)$ 走到 $(2,n)$。

(注：$k=1$ 或 $k=n$ 是这个模型的特例，也是成立的)

所以，一个 $f(l,r)$ 中存在路径，当且仅当存在至少一个 $k \in [1, n]$，使得路径 $k$ 上的所有格子都为 $1$。

路径 $k$ 包含了哪些格子？

• 第一行的前 $k$ 个：$(1,1), (1,2), \dots, (1,k)$

• 第二行的后 $n-k+1$ 个：$(2,k), (2,k+1), \dots, (2,n)$

步骤 2：分析 $(l,r)$ 的条件 (Condition)

对于一个固定的 $k$，要让“路径 $k$”上所有格子都为 $1$， $l$ 和 $r$ 必须满足什么条件？

• $b_{i,j}$ 为 $1$ $\iff$ $l \le a_{i,j} \le r$

• 所以，对于路径 $k$ 上的所有格子 $(i,j)$，都必须满足 $l \le a_{i,j} \le r$。

这等价于：

1. $l \le$ 路径 $k$ 上所有 $a_{i,j}$ 的最小值。

2. $r \ge$ 路径 $k$ 上所有 $a_{i,j}$ 的最大值。

我们来定义两个值：

• $L(k) = \min(a_{1,1}, \dots, a_{1,k}, a_{2,k}, \dots, a_{2,n})$

• $R(k) = \max(a_{1,1}, \dots, a_{1,k}, a_{2,k}, \dots, a_{2,n})$

所以，一个 $(l,r)$ 对能激活路径 $k$ $\iff$ $l \le L(k)$ 且 $r \ge R(k)$。

步骤 3：分析你的 WA2 代码

我们先来看看你WA的代码里计算了什么：

• premax[i] / premin[i] 是 $a_{1,1}, \dots, a_{1,i}$ 的最大/最小值。

• sufmax[i] / sufmin[i] 是 $a_{2,i}, \dots, a_{2,n}$ 的最大/最小值。

你在循环里计算的：

• mi = min(premin[i], sufmin[i]) 这就是 $L(i)$！

• mx = max(premax[i], sufmax[i]) 这就是 $R(i)$！

非常好！ 你的代码正确地计算出了所有 $n$ 个路径的 $L(k)$ 和 $R(k)$。

但你的错误在这里：

C++

l=max(l,mi), r=min(r,mx);

你最后计算的 l 是 $\max(L(1), \dots, L(n))$，而 r 是 $\min(R(1), \dots, R(n))$。

这组 $(l,r)$ 没有任何意义。题目要求我们统计的是：

“所有在 $k=1$ 的 $(l,r)$ 集合” $\cup$ “所有在 $k=2$ 的 $(l,r)$ 集合” $\cup$ ... $\cup$ “所有在 $k=n$ 的 $(l,r)$ 集合”

这个并集的大小。

你计算的不是并集，也不是交集，而是一个不相关的奇怪值。

---

步骤 4：如何正确统计“并集”？

直接计算 $n$ 个“矩形区域” $(l \le L(k), r \ge R(k))$ 的并集很复杂（需要容斥原理）。

jiangly 的代码用了一个极其巧妙的逐行扫描思想，把一个二维的“面积并”问题，转换成了一个一维的求和问题。

我们不直接统计 $(l,r)$ 对，我们换个角度：

遍历所有的 $l \in [1, 2n]$，对于每个 $l$，我们去数有多少个 $r$ 能和它配对。

一个 $(l,r)$ 对是合法的，当且仅当：

$\exists k$ 使得 $l \le L(k)$ 且 $r \ge R(k)$。

固定 $l$：

• $l$ 必须“支持”至少一条路径。我们只关心那些 $k$，使得 $L(k) \ge l$。

• 对于所有 $l$ 支持的 $k$ (即 $L(k) \ge l$ )， $r$ 只要 $\ge$ 它们中任意一个 $R(k)$ 就行了。

• 为了让 $r$ 的选择尽可能多，$r$ 只需要 $\ge \min \{ R(k) \mid L(k) \ge l \}$。

• (我们还知道 $r \ge l$。但因为 $R(k) \ge L(k) \ge l$，所以 $\min \{ \dots \} \ge l$ 自动成立。所以 $r \ge l$ 这个条件可以忽略)。

我们定义一个函数 $f(l) = \min \{ R(k) \mid L(k) \ge l \}$。

如果不存在 $k$ 使得 $L(k) \ge l$，我们就让 $f(l) = 2n+1$ (一个哨兵值)。

• 对于一个 $l$，只要 $r \ge f(l)$ 且 $r \le 2n$，这对 $(l,r)$ 就是合法的。

• 所以，对于 $l$，合法的 $r$ 的数量是：$2n - f(l) + 1$ (如果是负数，则为 0)。

最终答案 = $\sum_{l=1}^{2n} \max(0, 2n - f(l) + 1)$

步骤 5：jiangly 的代码如何实现？

jiangly 的代码就是为了高效计算 $f(l)$ 函数。

(注意：jiangly 的代码将所有 $a_{i,j}$ 都减了 $1$，所以他是 0-indexed，值域是 $0 \sim 2n-1$。我们的 $f(l)$ 对应他的 $f[i]$)

1. 初始化 f 数组：

   C++

   std::vector<int> f(2 * n, 2 * n);
   

   f 数组的下标代表 $l$，值代表 $f(l)$。初始化为 $2n$ (他的“无穷大”)。

2. 计算 $L(k)$ 和 $R(k)$，并更新 f：

   C++

   for (int i = 0; i < n; i++) {
       int L = std::min(pmin[i], smin[i]); // 这就是 L(k)
       int R = std::max(pmax[i], smax[i]); // 这就是 R(k)
       f[L] = std::min(f[L], R);
   }
   

   这一步之后，f[l] 存储的是 $\min \{ R(k) \mid L(k) = l \}$。

   (即：所有 $L(k)$ 恰好等于 $l$ 的路径 $k$ 中，最小的那个 $R(k)$)

3. 计算 $f(l)$：

   我们想要的 $f(l) = \min \{ R(k) \mid L(k) \ge l \}$。

   而我们现在有 $f'[l] = \min \{ R(k) \mid L(k) = l \}$。

   $f(l)$ 其实就是 $f'[l], f'[l+1], f'[l+2], \dots$ 里的最小值。

   这不就是后缀最小值 (Suffix Minimum) 吗！

   C++

   for (int i = 2 * n - 2; i >= 0; i--) {
       f[i] = std::min(f[i], f[i + 1]);
   }
   

   这个循环跑完，f[i] 就存着 $f(i)$ 的真正值了。

4. 求和：

   C++

   i64 ans = 0;
   for (int i = 0; i < 2 * n; i++) {
       ans += 2 * n - f[i];
   }
   

   (因为 $f[i]$ 不可能 $> 2n$，所以 $\max(0, \dots)$ 可以省略。$2n - f[i]$ 就对应 1-indexed 的 $2n - f(l) + 1$)。

总结与提升

1. 你的 WA2 原因： 你正确计算了 $n$ 个 $(L(k), R(k))$ 对，但你错误地将它们“合并”了。你没有意识到你要求的是 $n$ 个条件集的并集。

2. 本题核心能力：

   • 模型转换： 将一个二维的“路径”问题，转换为 $n$ 个一维的“路径 $k$”问题。

   • 计数问题转换： 将一个“二维区域并集”的计数问题，转换为“一维逐行扫描”的求和问题。 (即 $\sum_{l} \text{count}(r)$)

   • 算法实现： 利用“后缀最小值”来快速计算 $\min \{ R(k) \mid L(k) \ge l \}$。

这个思维转换（从 count(l,r) 转换到 $\sum_l \text{count}(r)$）在 $1600 \sim 1900$ 分段的计数题中极其常见。这个技巧一定要掌握。

这个分析对你有帮助吗？你想不想把你 WA 的代码，按照这个思路修改一下试试？

对于细节问题的考量

1. f[L] = min(R, f[L]); 这一步

• 目的： 这个循环把 f 数组当作一个“桶”或“映射表”来使用。

• 索引 (L)： 索引 L 代表一个特定的最小 $l$ 需求（即路径 $k$ 的 $L(k)$ 值）。

• 值 (R)： 存储的值 f[L]，代表在所有 $L(k)$ 正好等于 L 的路径 $k$ 中，那个最小的 $R(k)$ 需求是多少。

• 示例： 如果路径 3 的 $(L=5, R=10)$，路径 7 的 $(L=5, R=8)$，那么这个循环跑完后，f[5] 的值会是 8。这只是一个中间步骤。

2. 后缀最小值步骤：f[i] = min(f[i], f[i+1]);

• 目的： 这个循环将 f 数组从它的中间状态（上一步的结果）转换为我们计数所需的最终状态。

• 之前： f[i] = $\min \{ R(k) \mid L(k) = i \}$ （只考虑那些 $L(k)$ 等于 $i$ 的路径）。

• 之后： f[i] = $\min \{ R(k) \mid L(k) \ge i \}$ （考虑所有 $L(k)$ 是 $i, i+1, i+2, \dots$ 的路径）。

• 原因： 当我们检查一个给定的 $l=i$ 时，我们被允许使用任何一条 $L(k)$ 需求被满足的路径 $k$（即 $L(k) \ge l=i$）。这个循环的目的就是从所有这些合法的路径中，找出那个要求最低的 $R(k)$（即最小的 $R(k)$）。

3. 为什么 1-Indexed 要 +1，而 0-Indexed 不需要

这是一个非常经典的、关于计算闭区间 $[A, B]$ 内整数个数的“差一”细节。计算公式永远是：$\text{个数} = B - A + 1$。

• 你的 1-Indexed（1 为起始）代码：

  • 数值范围：$[1, 2n]$

  • $l$ 是 $i$，$r$ 必须在 $[f[i], 2n]$ 范围内

  • $A = f[i]$, $B = 2n$

  • 个数 = $(2n) - f[i] + 1$

• jiangly 的 0-Indexed（0 为起始）代码：

  • 数值范围：$[0, 2n-1]$

  • $l$ 是 $i$，$r$ 必须在 $[f[i], 2n-1]$ 范围内

  • $A = f[i]$, $B = 2n-1$

  • 个数 = $(2n-1) - f[i] + 1$

  • 化简后：$2n - f[i]$

那个 +1 并没有消失；它只是在 0-Indexed 的情况下，被上界 $2n-1$ 中的那个 -1 给数学上抵消了。两种方法都正确地应用了同一个计数原理。

这道题目在考什么

这是一个非常好的问题。你开始从“做对一道题”转向“从一道题学到东西”，这是冲上 1600 分最关键的思维转变。

这道 Monopati 题是一道绝佳的 1600 分“守门员”题。它不（直接）考察你背诵的某个复杂算法（比如 KMP 或 Dijkstra），而是纯粹考验你的思维能力。

---

🧐 这道题在考验什么？

它主要考验你三个层次的能力：

1. 问题建模能力 (Modeling)：

   • 这是最重要的一步。一个“从 (1,1) 到 (2,n) 的右下路径”听起来很复杂，可能有成千上万条。

   • 你的第一个突破是必须意识到，任何这样的路径都必然是在某一列 $k$ 从第一行“掉到”第二行。

   • 因此，这个模糊的“路径”问题被你转化（model）成了 $n$ 个清晰、具体、独立的“路径 $k$”问题。这是从 1200 到 1600 的最大思维鸿沟之一：将模糊的描述转化为清晰的数学/逻辑模型。

2. 约束分析能力 (Constraint Analysis)：

   • 当你有了 $n$ 个“路径 $k$”模型后，你对每一个模型进行了分析。

   • “路径 $k$ 上的所有格子都为 1”这个条件，被你转化成了一个数学约束：$l \le L(k)$ 且 $r \ge R(k)$。

   • 这又是一次转化，你把一个网格问题，变成了 $n$ 个二维平面上的“矩形区域”问题。

3. 高效计数能力 (Efficient Counting)：

   • 这是最精妙的一步，也是区分 1400 和 1600+ 的地方。

   • （慢速思路） 遍历 $O(n^2)$ 个 $(l,r)$ 对，看每个 $(l,r)$ 是否满足至少一个 $k$ 的约束。 $\rightarrow$ 太慢。

   • （你的 AC 思路） 题目要求的是 $n$ 个“矩形区域”的并集面积。直接求并集很复杂。

   • 你采用了我们讨论的“逐行扫描”思想：不直接数 $(l,r)$ 对，而是去 $\sum_{l=1}^{2n} \text{count}(r)$。

   • 为了高效计算 $\text{count}(r)$，你又用了 $O(n)$ 预处理 + $O(n)$ 后缀最小值，最终用 $O(n)$ 时间解决了问题。这背后的“后缀最小值”和“桶排序”的思想，都是非常高级的技巧。

总结： 这道题考验你连续两次将问题转化的能力，以及用一个巧妙的（基于后缀的）数据处理技巧来优化计数的能力。

---

🚀 为了上 1600，你应该做哪些努力？

基于你对这道题的分析，你已经具备了冲 1600 的潜力。你需要的是把这种能力系统化：

1. 掌握核心“思维工具”（而不只是算法模板）

   • 你现在处在 1200 分，你可能已经会了 sort, binary_search (函数), vector, map。

   • 1600 分要求你在“想不到”的地方使用它们。

   • 二分答案 (Binary Search on Answer)： 当题目要求“最大化最小值”或“最小化最大值”时，几乎总是二分答案。

   • 双指针 (Two Pointers / Sliding Window)： 在 $O(n)$ 时间内处理“满足某个条件的连续子数组”问题。

   • 前缀和/差分 (Prefix Sums / Difference Arrays)： $O(1)$ 查询区间和， $O(1)$ 区间修改（配合差分）。这是 Monopati 中 $L(k)$ 和 $R(k)$ 能快速计算的基础。

2. 练习“建模”能力（就像这道题一样）

   • 1600 分的题很少会直接说“请用 DP”或“请用二分”。

   • 题目会是一个故事，比如“小明种花”、“怪兽入侵”。你的首要任务是把故事扒掉，看它是不是在描述一个你熟悉的模型（如图论、DP、二分）。

   • 练习方法： 专门去做 CF 1400-1700 分的 C 题和 D 题。看题解时，不要只看代码，要看题解的第一句话（比如：“我们可以注意到...这是一个二分问题”）。然后关掉题解，自己想为什么这是一个二分问题。

3. 坚持“Upsolving”（补题）

   • 这是最最最重要的一条。你的 rating 提升不是发生在比赛中，而是发生在比赛后。

   • 规则： 每打完一场 CF 比赛，你必须（在 2-3 天内）把你没做出来的、以及你做出来了但比别人慢的题，全部看懂并重写一遍。

   • 特别是 C 题和 D 题。你今天对 Monopati (C 题) 的深入分析，就是一次完美的 Upsolving。

4. 学习基础数据结构

   • 要稳定在 1600，有一些工具你必须会用：

   • 并查集 (DSU): 维护连通性问题（“A 和 B 是不是亲戚？”）。

   • 树状数组 (BIT) / 线段树 (Segment Tree): 它们是“前缀和”的超级升级版。能做到 $O(\log n)$ 单点修改 和 $O(\log n)$ 区间查询。Monopati 里的后缀最小值，其实也可以用线段树来 $O(n \log n)$ 解决（虽然 $O(n)$ 更好）。

你今天对 C 题的深入分析（特别是你问的 3 个细节问题）非常棒，这正是 1600 分选手所具备的思考能力。你已经走在正确的路上了。

我们是继续分析下一道题，还是你想选一个刚才提到的“思维工具”（比如“二分答案”或“双指针”），我们找一道题来专门练习一下？

CF 题解思路

我们称一对整数 $(l, r)$ 是好的，当且仅当 $1 \le l \le r \le 2n$ 并且在 $f(l, r)$ 中存在一条从 $(1, 1)$ 到 $(2, n)$ 的、由值为 $1$ 的单元格组成的右下路径。对于某个固定的左端点 $l$（从 $1$ 到 $2n$），令 $r_l$ 表示使得数对 $(l, r_l)$ 是好的最小整数。如果不存在这样的整数，为方便起见，我们记 $r_l = n+1$。

第一个观察是：如果 $(l, r)$ 是好的，并且 $r < 2n$，那么 $(l, r+1)$ 也是好的。原因很明显：在 $f(l, r)$ 中值为 $1$ 的每个单元格，在 $f(l, r+1)$ 中值也为 $1$。因此，如果我们找到了 $r_1, r_2, \ldots, r_{2n}$，那么答案将是 $(2n - r_1 + 1) + (2n - r_2 + 1) + \ldots + (2n - r_{2n} + 1)$。（换句话说，我们是在计算所有数对 $(l, r_l), (l, r_l+1), \ldots, (l, 2n)$，其中 $1 \le l \le 2n$）。

第二个观察随之而来：$r_1 \le r_2 \le \ldots \le r_{2n}$。很明显，网格 $f(l, r_l)$ 和 $f(l+1, r_l)$ 之间的唯一区别是，$f(l+1, r_l)$ 中值为 $0$ 的单元格数量相同或更多，并且如果某个单元格在 $f(l+1, r_l)$ 中值为 $1$，那么它在 $f(l, r_l)$ 中值也为 $1$。如果我们在 $f(l+1, r_l)$ 中不再有右下路径，那么对于所有 $r \le r_l$，在 $f(l+1, r)$ 中都没有右下路径。由此可得 $r_{l+1} \ge r_l$。

这个观察允许我们使用双指针。对于某个固定的 $l$ 和 $r$，如果 $(l, r)$ 不是好的，我们将持续增加 $r$ 直到它变成好的，换句话说就是找到 $r_l$。我们激活所有值为 $r+1$ 的单元格。为了检查数对 $(l, r+1)$ 是否是好的，我们找到第一行中第一个未激活的单元格和最后一行中最后一个未激活的单元格（如果一个单元格不在我们当前考虑的范围内，则它是未激活的）。这可以通过维护两组未激活的单元格来完成，每组对应一行。假设它们分别位于列 $a$ 和 $b$。那么，在 $f(l, r+1)$ 中存在一条右下路径当且仅当 $a - 1 > b$（我们可以到达单元格 $(1, a-1)$，然后转到单元格 $(2, a-1)$，再继续到 $(2, n)$）。一旦我们找到 $r_l$，我们将增加 $l$，停用所有值为 $l$ 的单元格，并持续增加 $r_l$ 直到我们找到 $r_{l+1}$，依此类推。

CF 题解代码

// nifeshe

#ifdef LOCAL
    #include <bits/include_all.h>
#else
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
#endif

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const ll mod = 998244353;
const ll inf = 1e18;
const int MAX = 2e5 + 42;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n));
    for(auto &i : a) {
        for(auto &j : i) {
            cin >> j;
        }
    }

    vector<vector<pii>> pos(2 * n + 1);
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < n; j++) {
            pos[a[i][j]].push_back({i, j});
        }
    }


    array<set<int>, 2> st;
    st[0].insert(inf);
    st[1].insert(-inf);
    for(int i = 0; i < n; i++) st[0].insert(i);
    for(int i = 0; i < n; i++) st[1].insert(i);

    auto add = [&](int x) {
        for(auto [i, j] : pos[x]) {
            st[i].erase(j);
        }
    };

    auto del = [&](int x) {
        for(auto [i, j] : pos[x]) {
            st[i].insert(j);
        }
    };

    auto check = [&]() {
        if(st[0].count(0)) return false;
        if(st[1].count(n - 1)) return false;
        if(*st[0].begin() - 1 <= *st[1].rbegin()) return false;

        return true;
    };

    int ans = 0;
    int r = 0;
    for(int l = 1; l <= 2 * n; l++) {
        while(r + 1 <= 2 * n && !check()) {
            add(++r);
        }
        if(!check()) break;

        ans += 2 * n - r + 1;
        del(l);
    }

    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}