題目大意:給定一個由1和2組成的序列,多次詢問是否存在一個區間滿足區間和=
如果
如果存在一個前綴和為
否則一定存在一個前綴和
然後我們將左右端點同時右移 顯然如果某一時刻
記錄
如果
如果
否則無解
#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;
}