目录

• $\text{Rings}$
  • 解法
• $\text{Two Hundred Twenty One}$
  • 解法
  • 代码

\(\text{Rings}\)

解法

先开始想了一堆杂七杂八的情况，但实际上一个 \(0\) 就够了…

• 串中没有 \(0\)。直接选 1 n-1 2 n。
• 有在 \(i\in[1,n/2]\) 中的 \(0\)。选 i n i+1 n。
• 有在 \(i\in[n/2+1,n]\) 中的 \(0\)。选 1 i 1 i-1。

\(\text{Two Hundred Twenty One}\)

解法

观察样例我们可以发现答案只有 \(0,1,2\)。预处理前缀和 \(pre_i\)。考虑最终序列长度一定是偶数，我们不妨做出以下猜想：

• \(pre_r-pre_{l-1}=0\)。这个其实也不用猜也知道答案是 \(0\)。
• 长度为偶数。答案是 \(2\)。而且这也是答案最小的情况。
• 长度为奇数。答案是 \(1\)。而且这也是答案最小的情况。

长度为偶数的序列随便删一个就是奇数的情况，所以我们只用证明长度为奇数答案是 \(1\) 即可。

由于删掉一个数后，它后面的和会取相反数，所以问题转化为能否找到一个数，它左右两边的和相等。

设 \(s=pre_r-pre_{l-1}\)。如果删掉的数 贡献 是 \(1\)，我们希望它左边的和是 \(\frac{s-1}{2}\)；如果删掉的数 贡献 是 \(-1\)，我们希望它左边的和是 \(\frac{s+1}{2}\)。而这两个数在 \(0\) 到 \(s\) 之间，且一个数只会让序列和变化 \(1\) 或 \(-1\)，所以必定是有解的。

如何构造长度为奇数的答案？用 g[0/1][V] 存储贡献为 \(1\) 或 \(-1\)，前缀和到这一位是 \(V\) 的所有 \(i\)。对于每个询问在对应的 vector 里二分即可。需要注意实现时这两个数最好用整除，不然可能会出现 \(\mathtt{qqgg}\) 的问题。

代码

#include <cstdio>
#define print(x,y) write(x),putchar(y)

template <class T>
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while((s=getchar())>'9' or s<'0')
		f|=(s=='-');
	while(s>='0' and s<='9')
		x=(x<<1)+(x<<3)+(s^48),
		s=getchar();
	return f?-x:x;
}

template <class T>
inline void write(const T x) {
	if(x<0) {
		putchar('-'),write(-x);
		return;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
}

#include <vector>
#include <algorithm>
using namespace std;

const int maxn=3e5;

int n,q,pre[maxn+2];
char s[maxn+3];
vector <int> g[2][(maxn<<1)+5];
vector <int> :: iterator it;

void calc(int x,int y) {
	int s=pre[y]-pre[x-1];
	int r=(s-1>>1)+pre[x-1]+1;
	it=lower_bound(g[0][r+maxn].begin(),g[0][r+maxn].end(),x);
	if(it!=g[0][r+maxn].end() and *it<=y)
		return (void)(print(*it,'\n'));
	r=(s+1>>1)+pre[x-1]-1;
	it=lower_bound(g[1][r+maxn].begin(),g[1][r+maxn].end(),x);
	if(it!=g[1][r+maxn].end() and *it<=y)
		return (void)(print(*it,'\n'));
}

int main() {
	for(int T=read(9);T;--T) {
		n=read(9),q=read(9);
		scanf("%s",s+1);
		for(int i=1;i<=n;++i) {
			pre[i]=pre[i-1]+(s[i]=='+'?1:-1)*((i&1)?1:-1);
			if((s[i]=='+' and (i&1)) or (s[i]=='-' and !(i&1)))
				g[0][pre[i]+maxn].push_back(i);
			else g[1][pre[i]+maxn].push_back(i);
		}
		while(q--) {
			int x,y;
			x=read(9),y=read(9);
			if(pre[y]-pre[x-1]==0)
				puts("0");
			else if((y-x)&1) {
				puts("2");
				print(x,' ');
				calc(x+1,y);
			}
			else {
				puts("1");
				calc(x,y);
			}
		}
		for(int i=1;i<=n;++i)
			if((s[i]=='+' and (i&1)) or (s[i]=='-' and !(i&1)))
				g[0][pre[i]+maxn].clear();
			else g[1][pre[i]+maxn].clear();
	}
	return 0;
}