很牛的题。
首先转化题意：把 \(n + 1\) 拿出来，然后把 \(p_1 \sim p_n\) 依次放到 \(A\) 栈里，\(p_{2n + 1} \sim p_{n + 2}\) 依次放到 \(B\) 栈里。那么每次操作相当于先拿一个栈的栈顶到答案序列里，再删另一个栈的物品。那么我们假设答案有 \([l, r]\) 这个连续段，说明 \(l \sim r\) 的点都要选。那么我们枚举 \([l, r]\)，将 \([l, r]\) 中的点称作黑点，其它点称作白点。就需要选择所有黑点。
每次操作有如下三种情况：
- 栈顶为两个白点，删掉一个拿一个
- 栈顶为一黑一白，删掉白拿黑
- 栈顶为两个黑点，都拿掉，然后从两个栈里分别拿出一个白点，删掉。
那么删哪个呢？由于更接近栈底的白点更容易作为第三种情况中的选择，而更接近栈顶的白点容易被第一种情况拿掉，也就是说底下的白点更有用，于是可以贪心地维护，每次取最接近栈顶的白点删掉即可做到 \(\mathcal{O}(n)\)。双指针枚举 \(l, r\) 就做到了 \(\mathcal{O}(n^2)\)。
那么瓶颈在维护这个贪心的过程，考虑把它建模一下，对于一个点 \(x\)，记其和栈顶的距离为 \(d_x\)，那么对于一个白点 \(y\)，其可以作为所有 \(d_x \le d_y\) 的黑点 \(x\) 拿掉时删掉的点，我们把黑白点看成一个二分图 \((X, Y, E)\)，将 \(d_x \le d_y\) 的黑点 \(x\) 和白点 \(y\) 连边，那么有解就等价于存在 \(X\) -完美匹配。就可以套用 Hall 定理了。那么再转化一下，就是对于 \(A\) 的每个后缀（即栈底到某个点这一段）中的黑点个数都要 \(\le B\) 的这个后缀中白点的个数，同理对于 \(B\) 的每个后缀中的黑点个数都要 \(\le A\) 的这个后缀中白点的个数，但是显然满足了前者一定满足后者。每次移动 \([l, r]\) 相当于改变一个点的颜色，那么需要后缀加，查询全局 \(\min\) 是否 \(\ge 0\)，线段树即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 4e5 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, m, a[N], pos[N];
struct SegTree {#define ls (u << 1)#define rs (u << 1 | 1)#define mid ((l + r) >> 1)ll tr[N << 2], tag[N << 2];void pushup(int u) { tr[u] = min(tr[ls], tr[rs]); }void pushdown(int u) {if (!tag[u]) return ;tr[ls] += tag[u]; tr[rs] += tag[u];tag[ls] += tag[u]; tag[rs] += tag[u];tag[u] = 0;}void build(int l = 1, int r = n, int u = 1) {if (l == r) {tr[u] = l;return ;}build(l, mid, ls); build(mid + 1, r, rs);pushup(u);}void add(int x, int y, int v, int l = 1, int r = n, int u = 1) {if (x <= l && r <= y) {tr[u] += v; tag[u] += v;return ;}pushdown(u);if (x <= mid) add(x, y, v, l, mid, ls);if (mid < y) add(x, y, v, mid + 1, r, rs);pushup(u);}ll ask() { return tr[1]; }
} sgt;
void add(int x) {if (x == n + 1) return ;if (x < n + 1) sgt.add(x, n, -1);else sgt.add(m - x + 1, n, -1);
}
void del(int x) {if (x == n + 1) return ;if (x < n + 1) sgt.add(x, n, 1);else sgt.add(m - x + 1, n, 1);
}
void main() {cin >> n;m = n << 1 | 1;for (int i = 1; i <= m; i++) cin >> a[i], pos[a[i]] = i;sgt.build();int ans = 0;for (int l = 1, r = 0; l <= m; l++) {while (r <= m && sgt.ask() >= 0ll) ans = max(ans, r - l + 1), add(pos[++r]);del(pos[l]);}cout << ans << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}
// start coding at 11:16
// finish debugging at 11:53