Beginning

這道題思維難度很大，有兩個難點其實都不好解決，但因為其代碼太過弱智所以只是綠題。

本題解詳細地分析了做題時的歷程與思路，所以希望大家可以仔細地完整閱讀。

Analysis

首先先大體觀察一下題目的性質：$n$ 是排列，這可能會有用；題目的權值求法其實就是逆序對，而逆序對產生的貢獻一定有偶數個，所以我們的答案一定是偶數。

同時，對二取模也十分引人注意。這意味著我們的 $v$ 序列其實是一個 $01$ 序列。

題目要求可以選擇執行一次移動操作使得權值和變大，也就是我們要通過這一次操作嘗試變出更多的 $1$。嘗試一下發現，每次移動一個數只會對其移動中跨過的數產生影響，如果是 $01$ 序列的話就體現在會把 $01$ 翻轉。對于移動的數字，如果跨過了奇數個位置則翻轉，否則不變。

可以簡單理解一下：

1. 如果一個數 $x$ 從位置 $a$ 移動到位置 $b$ 和 $b+1$ 之間（滿足 $a<b$），那么對于 $[a+1,b]$ 中的任意一個數字 $t$，如果 $x$ 在移動前對 $t$ 產生了貢獻，則 $x>t$，移動后 $x$ 將不再對 $t$ 產生貢獻，在模二的意義下就相當于 $t$ 異或上 $1$，即 $01$ 翻轉。反之亦然。
2. 對于 $x$ 同理，其移動后原來產生貢獻的數字一定不產生貢獻，原來不產生貢獻的數字一定會產生新貢獻。看貢獻變化量的奇偶性，如果跨過偶數個那么貢獻變化量一定是偶數（偶數 - 偶數 = 偶數），在模二意義下貢獻值不變。反之亦然。

我們好像得到了一個初步的簡化題面：給定一個 $01$ 序列，可以翻轉某一個區間，使得最終序列中 $1$ 個數最多。

顯然，我們要求一個類似最大子段和的東西，然后用初始貢獻加上一次翻轉能帶來的最大貢獻就是答案。

同時我們還發現翻轉區間的長度只能是偶數，因為上述 $x$ 跨過奇數個位置的情況下 $x$ 自己也會變，其實就等價于翻轉了 $[a,b]$ 這個長度為偶數的區間。

所以我們要找到一個長度為偶數的區間使得區間內 $0$ 的個數減去 $1$ 的個數得到的差最大。

考慮把 $0$ 映射成 $1$，把 $1$ 映射成 $?1$，然后統計前綴和。對于每個位置，可以記錄下之前奇數位置與偶數位置上的最小前綴和，根據下標奇偶性轉移最大差值即可。

時間復雜度 $O(n)$。

---

這還沒完，轉換完題意后我們還要考慮如何計算初始貢獻。這道題時限卡樹狀數組的 $\log$（實測光放一個 sort 交上去就會 TLE），所以我們還要考慮如何線性求初始貢獻。

肯定要從對二取模這個性質下手。發現我們最開始得到的逆序對貢獻數一定是偶數這個結論其實很對，假設對于 $p_i$，因為是排列所以比 $p_i$ 小的數就有 $p_i?1$ 個。設 $t_i$ 表示 $i$ 左邊比 $p_i$ 小的數的個數，根據題目貢獻可以寫成 $[(i?1)?t_i]+[(p_i?1)?t_i]=i+p_i?(2t_i+2)$，后半部分明顯被取模二約掉了！所以最終的初始貢獻表達式即為 $v_i=(i+p_i)\mathrm{mod}2$。

根據上述方法預處理即可，時間復雜度 $O(n)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e6 + 7;int n, a[maxn], s[maxn];void solve()
{int ans = 0;cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];a[i] = (i + a[i]) % 2; // 計算初始值ans += (a[i] == 1); // 統計答案s[i] = s[i - 1] + (a[i] == 0? 1 : -1); // 轉化+預處理前綴和}int min1 = 1e9, min2 = 0; // 奇數、偶數位置的最小前綴和int maxd = 0; // 最大貢獻for(int i = 1; i <= n; i ++){if(i % 2 == 0){maxd = max(maxd, s[i] - (i==2? 0:min2)); // 特判一下之前還沒有前綴和的時候可以認為能全選（歷史前綴和=0）min2 = min(min2, s[i]);}else{maxd = max(maxd, s[i] - (i==1? 0:min1));min1 = min(min1, s[i]);}}cout << ans + maxd << '\n';
}signed main()
{ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);int T; cin >> T;while(T --) solve();return 0;
}