题目大意：给定一个由1和2组成的序列，多次询问是否存在一个区间满足区间和=
x
如果
x>sum
显然无解
如果存在一个前缀和为
x
则直接输出
否则一定存在一个前缀和
[1,i]
等于
x+1
然后我们将左右端点同时右移 显然如果某一时刻
a[l]=1
或者
a[r+1]=1
那么我们就找到解了
记录
exti
表示从
i
开始有多少个连续的
2
如果
ext1
，那么解为
[1+ext1+1,i+ext1]
如果
ext1≥exti
且
i+exti≠n+1
，那么解为
[1+exti,i+exti]
否则无解
O(n)
预处理所有答案即可
#include
#include
#include
#include
#define M 2002002 using namespace std; int n,m,sum; char s[M>>1]; int ext[M],l[M],r[M]; int main() { int i,x; cin>>n>>m; scanf("%s",s+1); for(i=n;i;i--) { ext[i]=ext[i+1]+1; if(s[i]=='W') ext[i]=0; } for(i=1;i<=n;i++) { sum+=s[i]=='W'?1:2; l[sum]=1;r[sum]=i; if(s[i]=='T') { if(ext[1]
sum || !l[x] ) puts("NIE"); else printf("%d %d\n",l[x],r[x]); } return 0; }