传送门
标签：构造、数学
题意
给你一个长为 \(2 \times n\) 的数列 \(a\)，满足 \(\forall i \in [1, 2 \times n], a_i \in [0, n]\)。
求一个区间，可以将区间中的数划分到两个集合，满足两个集合中数的和相同。
思路
考虑分析题目研究的组合对象，是一个区间。
考虑这个操作的数学刻画，就是给区间 \([l,r]\) 中的数赋一个权值 \(-1\) 或 \(+1\)，然后求一个和为 \(0\) 的区间。
此时，先别管赋权值，将区间和转换为前缀和，就是找到两个相等的前缀和。
思考，存在两个相等的对象，可以让我们联想到抽屉原理。
我们有 \(2 \times n + 1\) 个前缀和，也就是说我们要前缀和的值域在 \(2 \times n\) 种中才可以。
我们考虑将前缀和压在值域 \((-n,n]\) 中，显然这样就满足条件了。
这时，再回去看赋权值的事情，我们每次这样更新 \(sum\)：
\[sum \leftarrow
\begin{cases}
sum + a_i, & sum \le 0 \\
sum - a_i, & sum \gt 0
\end{cases}
\]
然后就做完了。
确实是很有意思的一道题。
赛时是没用想到赋权值，想到之后的转换其实是很自然的。
然后联想到抽屉原理又是一个思维难点。
总之，不要一直想着什么代码和数据结构的事情，要专心研究数学对象，怎么维护是后面的事情，思维不能跳来跳去。
代码
link
const int N = 2e6 + 5;
int n;
int a[N];
int sum[N];
int id[N * 2];
void solve_test_case(){n = read();rep(i, 1, 2 * n) a[i] = read();memset(id, -1, sizeof(id));id[n] = 0;int idl = 0, idr = 0;rep(i, 1, 2 * n){if(sum[i - 1] > 0) sum[i] = sum[i - 1] - a[i];else sum[i] = sum[i - 1] + a[i];if(~id[sum[i] + n]){idl = id[sum[i] + n] + 1;idr = i;break;}id[sum[i] + n] = i;}write(idl, ' '), write(idr);int tmp = sum[idl - 1];rep(i, idl, idr){if(tmp > 0){tmp -= a[i];putchar('0');}else{tmp += a[i];putchar('1');}}
}