CodeForces - 1562D2 Two Hundred Twenty One (hard version)(二分)

题目链接：点击查看

题目大意：定义一个前缀和公式 $a_1-a_2+a_3-a_4+\dots =\sum _{i=1}^n(-1{)}^{i-1}\cdot a_i$，再给出一个长度为 $n$ 的序列，只包含 { − 1 , 1 } \{-1,1\} {−1,1}，然后 $q$ 次询问，每次需要回答最少删除多少个数字可以使得区间 $[l,r]$ 的前缀和等于 $0$

题目分析：感觉 $D1$ 和 $D2$ 结合起来一起考真的不错。证明的话我不会，可以右转官方题解。

如果直接放 $D2$ 的话可能让人无从下手，但是放了一个 $D1$ 可以猜出一个差不多的结论，首先设 $sum[i]$ 是按照题目给出的公式的前缀和，下文中的区间和指的都是这个 $sum$：

1. 若 $[l,r]$ 的区间和等于 $0$ 的话，答案为 $0$
2. 若区间长度为奇数的话，答案为 $1$
3. 其他情况下答案为 $2$

这也就告诉我们，奇数情况下一定有解，偶数情况下，可以通过随便删掉一个数字然后变成奇数情况。

其实题目中的公式将加号藏起来了不太好看，如果将加号展开的话公式变成了（以 $n=5$ 为例）：
$$a_1+(-a_2)+a_3+(-a_4)+a_5$$

分两种情况讨论，首先删掉一个奇数位置，这里删掉 $a_3$ 后，新的序列变成了：
$$a_1+(-a_2)+a_4+(-a_5)$$

不难发现如果想要让 $a_1+(-a_2)+a_4+(-a_5)=0$，则需要满足 $a_1+(-a_2)=(-a_4)+a_5$

删掉偶数位置亦是如此，假设删掉 $a_2$ 后，新的序列变成了：
$$a_1+(-a_3)+a_4+(-a_5)$$

同理需要满足 $a_1=a_3+(-a_4)+a_5$

推广一下，在区间 $[l,r]$ 中（保证 $r-l+1$ 是奇数）如果删掉 $x$ 可以满足题意，那么删掉 $x$ 后，需要满足 $$sum[r]-sum[x]=sum[x-1]-sum[l-1]$$

移一下项得到 $$sum[r]+sum[l-1]=sum[x]+sum[x-1]$$

将 $sum[x]+sum[x-1]$ 的位置扔到桶里去对于每次询问直接二分答案就好啦

代码：

// Problem: D2. Two Hundred Twenty One (hard version)
// Contest: Codeforces - Codeforces Round #741 (Div. 2)
// URL: https://codeforces.com/contest/1562/problem/D2
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
#define lowbit(x) (x&-x)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
template<typename T>
inline void read(T &x)
{
	T f=1;x=0;
	char ch=getchar();
	while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	x*=f;
}
template<typename T>
inline void write(T x)
{
	if(x<0){x=~(x-1);putchar('-');}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int inf=0x3f3f3f3f;
const int N=1e6+100;
char s[N];
int sum[N];
map<int,vector<int>>node;
int cal(int l,int r) {
	int x=sum[r]+sum[l-1];
	return *lower_bound(node[x].begin(),node[x].end(),l);
}
int main()
{
#ifndef ONLINE_JUDGE
//	freopen("data.in.txt","r",stdin);
//	freopen("data.out.txt","w",stdout);
#endif
//	ios::sync_with_stdio(false);
	int w;
	cin>>w;
	while(w--) {
		node.clear();
		int n,m;
		read(n),read(m);
		scanf("%s",s+1);
		for(int i=1;i<=n;i++) {
			sum[i]=sum[i-1]+(i%2?1:-1)*(s[i]=='+'?1:-1);
			node[sum[i]+sum[i-1]].push_back(i);
		}
		while(m--) {
			int l,r;
			read(l),read(r);
			if(sum[r]-sum[l-1]==0) puts("0");
			else if((r-l+1)&1) {
				puts("1");
				printf("%d\n",cal(l,r));
			} else {
				puts("2");
				printf("%d %d\n",l,cal(l+1,r));
			}
		}
	}
	return 0;
}