Codeforces Round #741 Two Hundred Twenty One 题解 (Java/C++)

题解

首先，我们令$b[i]=a[i]\cdot (-1)^{(i-1)}$，$sum(l,r)=\sum_{i=l}^r{b[i]}$。

于是对于任意的i，b[i]要么是1要么是-1。因此如果最后的和为0，那么必然有1的数目和-1的数目相同。于是必然有，如果要和为0，那么这个区间的长度必为偶数。

先说结论：当原区间长度为奇数时，只需要删去一个数，就可让区间和为0。当原区间长度为偶数时，需要先删去一个数构成奇数长度，也就是总共需要删去两个数。当然，如果原区间和本身就是0，则不需要删除任何数。

我们考虑证明：

接着我们考虑在[l,r]中，删去下标为x的数。我们发现删去之后，sum(l,x-1)其实不会受到任何影响，而sum(x+1,r)的值正好需要乘以-1。
于是我们得到，如果删去x后，区间的和为0，则必有sum(l,x-1)=sum(x+1,r)。

现在，不妨假设原先sum(l,r)>0，且r-l+1为奇数。
此时，我们令x=r，也就是我们删去最右边的数。此时，如果sum(l,x-1)=0，那这个就是我们要的答案。因此我们只考虑sum(l,x-1)>0的情况。
接着，我们令x=r-1。考虑x左右两侧的区间和，我们发现：sum(l,x-1)-sum(x+1,r)的值随着x的变化而发生相应的变化。而变化的可能只有-2，0，2。
同时，我们注意到，当x移动到l时，sum(l,x-1)=0，sum(x+1,r)>0。
于是，随着x从r变道l，sum(l,x-1)-sum(x+1,r)由一个必然大于0的值，变成了一个必然小于0的值。而每次的变化只能是-2，0，2。因此必然存在这样一个x，使sum(l,x-1)-sum(x+1,r)=0。

于是，我们得到当r-l+1为奇数时，只需要删一个数即可。

现在剩下的问题就是如何找到这样的x，使得sum(l,x-1)-sum(x+1,r)=0。

我们将原等式变形后可以得到：sum(1,r)-sum(1,x)=sum(1, x-1)-sum(1,l-1)。进一步变形可得：sum(1,x)+sum(1, x-1)=sum(1,r)+sum(1,l-1)。

因此我们只需要维护一个前缀和，且在计算前缀和时，通过map记录sum(1,x)+sum(1, x-1)相应的下标。这样每次我们只需要查出所有和为sum(1,r)+sum(1,l-1)的下标，然后二分找出属于[l,r]之间的任意一个即可。

代码

Java

C++