我好弱智。
首先发现这东西根本不可做。考虑降值域！把 \(a_i\) 变成 \([a_i \ge k]\) 转化成 01 序列去做，那么最终的答案就是所有 \(k\) 得到的答案的 \(\max\)。
先考虑一个 01 序列怎么做。我们考虑求出每一个 \(0\) 到达它该到达的位置所需的时间 \(f_i\)。对于一个 \(0\)，我们有两种可能性：
- 在向左交换的过程中没有碰到任何一个 \(0\)；
- 在向左交换的时候碰到了一个 \(0\)。
我们发现，当交换过程中碰到一个 \(0\) 后，之后肯定是前一个 \(0\) 怎么走它就怎么走，于是答案就是 \(f_{i - 1} + 1\)；如果没有碰到任何一个 \(0\)，设这个数的位置为 \(t_i\)，那么它的答案就是前面的 \(1\) 的个数 \(k_i\)，再加上一个 \((t_i \bmod 1)\)（考虑第一次是否被交换）。即：
\[f_i = \max\{f_{i - 1} + 1, k_i + (t_i \bmod 1)\}
\]
设一共有 \(m\) 个 \(1\)，那么我们只需要考虑 \(f_m\) 即可。把上面的式子暴力展开，即可得到：
\[f_m = \max_{i=pre+1}^m \{k_i + (t_i \bmod 1) + (m - i)\}
\]
其中 \(pre\) 表示满足 \(f_i = 0\)（即一开始就已经在正确的位置）的前缀长度。
把它放到序列上维护，设第 \(i\) 个位置前面有 \(p_i\) 个 \(0\)，\(i - p_i\) 个 \(1\)，那么其实就是：
\[f_m = \max_{i=pre+1}^n \{[a_i = 0] (p_i + (i \bmod 1) + (m - (i - p_i)))\}
\]
\[f_m = \max_{i=pre+1}^n \{[a_i = 0] (2p_i + (i \bmod 1) + m - i)\}
\]
这东西很容易在线段树上维护，那么我们每次将一个 \(1\) 改为 \(0\)，直接维护即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, a[MAXN], p[MAXN];
struct SegmentTree {
struct Node {
int val, tag;
} t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
void tag(int i, int v) {
t[i].tag += v;
t[i].val += v;
}
void pushDown(int i) {
if (t[i].tag) {
tag(lc, t[i].tag);
tag(rc, t[i].tag);
t[i].tag = 0;
}
}
void add(int a, int b, int v, int i = 1, int l = 1, int r = n) {
if (a <= l && r <= b) {
tag(i, v);
return;
}
int mid = (l + r) >> 1;
pushDown(i);
if (a <= mid) add(a, b, v, lc, l, mid);
if (b > mid) add(a, b, v, rc, mid + 1, r);
t[i].val = max(t[lc].val, t[rc].val);
}
int query(int a, int b, int i = 1, int l = 1, int r = n) {
if (a > b) return -30 * n;
if (a <= l && r <= b) return t[i].val;
int mid = (l + r) >> 1;
pushDown(i);
if (b <= mid) return query(a, b, lc, l, mid);
if (a > mid) return query(a, b, rc, mid + 1, r);
return max(query(a, b, lc, l, mid), query(a, b, rc, mid + 1, r));
}
void build(int i = 1, int l = 1, int r = n) {
t[i].val = t[i].tag = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
}
} st;
int T;
bool b[MAXN];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
st.build();
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
p[a[i]] = i;
b[i] = 1;
}
st.add(1, n, -10 * n);
for (int i = 1; i <= n; i++) {
st.add(i, i, (i & 1) + i);
}
int pre = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
b[p[i]] = 0;
while (pre < n && !b[pre + 1]) pre++;
st.add(p[i], p[i], 10 * n);
st.add(p[i], n, -2);
ans = max(ans, i + st.query(pre + 1, n));
}
printf("%d\n", ans);
}
return 0;
}