思路与结论

• 只有“跨区间”的数对会受影响：

  • 新增逆序对：区间内的元素与区间右侧相同值形成的新逆序对（$a_i == a_j$ 且 $i$ 在区间内、$j$ 在区间右侧）。
  • 被消去的逆序对：区间左侧值为 $v+1$ 与区间内值为 $v$ 的数对（$a_p = a_q + 1$，$p$ 在区间左侧，$q$ 在区间内）。

• 将“选择区间 $[L,R]$ 并把区间内加 1”的收益定义为：

  • 收益 = 被消去对数 − 新增对数
  • 等价于：$sum_{q∈[L,R]} pre[L-1][a_q+1]$ − $sum_{q∈[L,R]} suf[R+1][a_q]$

• 线性求解（关键技巧）：

  • 右端点$R$一定要放在末尾，因为如果放在其它位置，右端点后的数可能会和区间里的数形成额外的逆序对

  • 从右到左把区间“向左扩展”。用两个数组维护：

    • rest[v]：当前还未划入区间/未处理的元素中，值为 v 的个数。
    • put[v]：已放入区间且“被视作 +1 后”的值为 v 的个数（即原来是 v-1）。

  • 当把位置 i 放入区间时（把 a[i] 视为被 +1）：

    • 被消去对数增加 rest[a[i]+1]（区间左侧与当前值成 (v+1, v)）。
    • 新增对数增加 put[a[i]]（当前值与右侧区间已放入、加一后的相同值）。
    • 将当前元素“记到加一后”的桶：put[a[i]+1] += 1。

  • 每步维护当前收益前缀的最大值，即为答案。

复杂度

• 时间复杂度：O(n) 每组（值域 ≤ n，数组统计）
• 空间复杂度：O(n)

Python 实现

import sys

def solve():
    it = iter(sys.stdin.read().strip().split())
    t = int(next(it))
    out = []
    for _ in range(t):
        n = int(next(it))
        a = [int(next(it)) for _ in range(n)]
        # 值域 ≤ n，开到 n+2 防止 a[i]+1 溢出
        cap = n + 2

        # rest[v]: 还未处理元素中值为 v 的个数（初始全体）
        rest = [0] * (cap + 1)
        for x in a:
            rest[x] += 1

        # put[v]: 已加入区间、并视作 +1 后的值为 v 的个数（原始值为 v-1）
        put = [0] * (cap + 1)

        cur = 0  # 当前把区间向左扩的累计收益
        best = 0 # 最大收益

        # 从右到左枚举左端点
        for i in range(n - 1, -1, -1):
            x = a[i]
            rest[x] -= 1
            # 增量 = 被消去对数 - 新增对数
            cur += rest[x + 1]
            cur -= put[x]
            # 把当前元素并入区间（加一后记到 x+1）
            put[x + 1] += 1
            if cur > best:
                best = cur

        out.append(str(best))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

Java 实现

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine().trim());
		while (T-- > 0) {
			int n = Integer.parseInt(br.readLine().trim());
			int[] a = new int[n];
			{
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
			}
			int cap = n + 2;
			int[] rest = new int[cap + 1]; // 未处理计数
			int[] put = new int[cap + 1];  // 已入区间且视作+1后的计数

			for (int x : a) rest[x]++;

			long cur = 0;  // 当前累计收益
			long best = 0; // 最大收益

			for (int i = n - 1; i >= 0; i--) {
				int x = a[i];
				rest[x]--;
				cur += rest[x + 1]; // 被消去对数增加
				cur -= put[x];      // 新增对数增加
				put[x + 1]++;       // 当前元素加入区间（视作 +1）
				if (cur > best) best = cur;
			}
			sb.append(best).append('\n');
		}
		System.out.print(sb.toString());
	}
}

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T; 
	if (!(cin >> T)) return 0;
	while (T--) {
		int n; cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) cin >> a[i];

		int cap = n + 2;
		vector<long long> rest(cap + 1, 0), put(cap + 1, 0);
		for (int x : a) rest[x]++;

		long long cur = 0, best = 0;
		for (int i = n - 1; i >= 0; --i) {
			int x = a[i];
			rest[x]--;
			cur += rest[x + 1]; // 被消去对数
			cur -= put[x];      // 新增对数
			put[x + 1]++;       // 进入区间后视作 +1
			if (cur > best) best = cur;
		}
		cout << best << "\n";
	}
	return 0;
}

题目内容

你有一个长度为 $n$ 的序列 $A:a_1,a_2,…,a_n$，你需要进行如下操作至多一次：

选择一个区间$[L,R](1≤L≤R≤n)$，将 $a_1,a_{L+1},...,a_R$ 全部加 $1$ 。即 $a_L,a_{L+1},...,a_R$ 均变为 $a_L+1,a_{L+1}+1,...,a_R+1$

设变化后的序列为 $B：b_1,b_2,…,b_n$，你需要最大化 $inv(A)-inv(B)$ ，其中 $inv()$ 函数表示该序列的逆序对数量，即满足 $i<j，a_1>a_j$ 的二元组 $(i,j)$ 个数。换句话说，你需要尽可能地减小序列 $A$ 的逆序对数量。

输入描述

第一行一个正整数 $T$ ，表示数据组数；

对于每一组数据，第一行一个正整数 $n$ ; 第二行 $n$ 个正整数 $a_1,a_2,...,a_n$，表示序列 $A$ 。

$1≤n≤10^5, 1≤T≤5, 1≤a_i≤n$

输出描述

对于每一组数据，输出一个整数，表示最大的 $inv(A)-inv(B)$ 。

样例1

输入

3
5
4 2 3 1 5
5
1 2 3 4 5
3
2 1 1

输出

2
0
2

说明

第一组数据，选择区间 $[3,4]$ ，变化后的序列为 $[4$,$2$,$4$,$2$,$5$,$5$] ，逆序对数量为3；变化前逆序对数量为 $5$ 。

第二组数据，选择任意区间都不会减小逆序对数量。

第三组数据，选择区间 $[2,3]$ ，变化后的序列为 $[2$,$2$,$2]$，逆序对数量为 $0$ ；变化前逆序对数量为 $2$ 。