小美的数对合并

[题目链接](https://www.nowcoder.com/practice/feea5d33fef743aeb718e4ab6fbaf9a2)

思路

给定长度为 的数组 ，对于满足 且 的点对 ，在 和 之间连一条无向边。求图中极大连通块的数量。

变量替换

令 ，则条件 等价于：

$$

因此，当 时， 之间有边当且仅当 ，即 数组在位置 上存在逆序对。

连通块一定是连续段

如果 （），那么对于任意 ：

  • 若 ，则 构成逆序对， 与 相连；
  • 若 ，则 ， 构成逆序对， 与 相连。

因此 和 之间的所有点都与 或 处于同一连通块。这说明连通块对应的下标集合一定是一段连续区间。

判断相邻位置是否属于同一连通块

位置 和 属于同一连通块，当且仅当存在 和 使得 ，即：

$$

令 ，。位置 和 之间断开（属于不同连通块）当且仅当 。

答案 = 断点数 + 1。

样例演示

输入 ，。

  • 位置 1-2：，，，不断开。
  • 位置 2-3：，，，不断开。
  • 位置 3-4：，，，断开。

断点数 = 1，答案 = 2。

输入 ，。

所有位置 ，全部断开。断点数 = 4，答案 = 5。

复杂度分析

  • 时间复杂度：，一次遍历计算后缀最小值，一次遍历统计断点。
  • 空间复杂度：，存储后缀最小值数组。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        vector<long long> b(n);
        for (int i = 0; i < n; i++) {
            long long a;
            scanf("%lld", &a);
            b[i] = a - (i + 1);
        }
        // suffix min
        vector<long long> smin(n);
        smin[n - 1] = b[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            smin[i] = min(smin[i + 1], b[i]);
        }
        int ans = 1;
        long long pmax = b[0];
        for (int i = 0; i < n - 1; i++) {
            if (pmax <= smin[i + 1]) {
                ans++;
            }
            pmax = max(pmax, b[i + 1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            long[] b = new long[n];
            for (int i = 0; i < n; i++) {
                long a = Long.parseLong(st.nextToken());
                b[i] = a - (i + 1);
            }
            long[] smin = new long[n];
            smin[n - 1] = b[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                smin[i] = Math.min(smin[i + 1], b[i]);
            }
            int ans = 1;
            long pmax = b[0];
            for (int i = 0; i < n - 1; i++) {
                if (pmax <= smin[i + 1]) {
                    ans++;
                }
                pmax = Math.max(pmax, b[i + 1]);
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}