CF1562 D2. Two Hundred Twenty One (hard version)

https://codeforces.com/problemset/problem/1562/D2

题意：
输出easy version的具体解

这是easy version题解
https://www.cnblogs.com/TheRoadToTheGold/p/15234002.html
用类似于求函数零点的方式找(b_i=0)的位置

#include<bits/stdc++.h>

#define N 300002

char s[N]; 
int a[N];

int sum(int l,int r)
{ 
	if(l&1) return a[r]-a[l-1];
	return a[l-1]-a[r];
}

int b(int pos,int l,int r)
{
	return a[pos-1]-a[l-1]+a[pos]-a[r];
}

void find(int l,int r)
{
	int ll=l,rr=r,mid;
	while(ll<=rr)
	{
		if(!b(ll,l,r)) 
		{
			printf("%d
",ll);
			return;
		}
		if(!b(rr,l,r)) 
		{
			printf("%d
",rr);
			return;
		}
		mid=ll+rr>>1;
		if(!b(mid,l,r))
		{
			printf("%d
",mid);
			return;
		}
		if(1ll*b(ll,l,r)*b(mid,l,r)>0) ll=mid+1;
		else rr=mid-1;
	}
}

int main()
{
	int T,n,m,l,r;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%s",&n,&m,s+1);
		for(int i=1;i<=n;++i) a[i]=s[i]=='+' ? 1 : -1;
		for(int i=1;i<=n;++i) 
			if(i&1) a[i]=a[i-1]+a[i];
			else a[i]=a[i-1]-a[i];
		while(m--)
		{
			scanf("%d%d",&l,&r);
			if(!sum(l,r)) printf("0
");
			else if((r-l)&1) 
			{
				printf("2
%d ",l);
				find(l+1,r);
			}
			else 
			{
				printf("1
");
				find(l,r);
			}
		}
	}
}