Description：

给一个只有 $1$ 和 $2$ 的序列，每次询问有没有一个子串的和为 $x$ 。

$1\leqslant n \leqslant 10^6$

Solution：

首先发现我如果找到了一个和为 $k$ 的子串，那么我就找到了一个 $k-2$ 的子串，因为他要么左边是二，直接去掉，要么右边是二，直接去掉，剩下只有一种可能，就是两边都是一，那就同时去掉两边，也就是说我可以得到所有比他小和他同奇偶的串，那么我们只要统计出这个奇偶性为某个值的最大子串和，然后依次消随便左边或右边，就可以预处理出所有方案，至于怎么统计某个奇偶性的最大子串，维护一个某个奇偶性的最小前缀和然后把每个位置的前缀和依次比较一下就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline char getc()

{

	register char c = getchar();

	while(c != 'T' && c != 'W')c = getchar();

	return c;

}

int n,m;

#define MAXN 1000010

int a[MAXN];

int sum[MAXN];

int l[2],r[2],minsum[2],pos[2],ans[2];

#define INF 0x3f3f3f3f

int res[MAXN][3];

int main()

{

	scanf("%d%d",&n,&m);

	char c;

	for(int i = 1;i <= n;++i)

	{

		c = getc();

		a[i] = (c == 'T' ? 2 : 1);

	}

	minsum[0] = 0;minsum[1] = 0x3f3f3f3f;

	pos[0] = 0;

	ans[0] = ans[1] = 0;

	for(int i = 1;i <= n;++i)

	{

		sum[i] = sum[i - 1] + a[i];

		if(sum[i] < minsum[sum[i] % 2])

		{

			minsum[sum[i] % 2] = sum[i];

			pos[sum[i] % 2] = i;

		}

		if(sum[i] - minsum[sum[i] % 2] > ans[(sum[i] - minsum[sum[i] % 2]) % 2])

		{

			ans[(sum[i] - minsum[sum[i] % 2]) % 2] = sum[i] - minsum[sum[i] % 2];

			r[(sum[i] - minsum[sum[i] % 2]) % 2] = i;l[(sum[i] - minsum[sum[i] % 2]) % 2] = pos[sum[i] % 2] + 1;

		}

		if(sum[i] - minsum[(sum[i] % 2) ^ 1] > ans[(sum[i] - minsum[(sum[i] % 2) ^ 1]) % 2])

		{

			ans[(sum[i] - minsum[(sum[i] % 2) ^ 1]) % 2] = sum[i] - minsum[(sum[i] % 2) ^ 1];

			r[(sum[i] - minsum[(sum[i] % 2) ^ 1]) % 2] = i;l[(sum[i] - minsum[(sum[i] % 2) ^ 1]) % 2] = pos[(sum[i] % 2) ^ 1] + 1;

		}

	}

	memset(res,0,sizeof(res));

	for(;l[0] <= r[0];)

	{

		res[sum[r[0]] - sum[l[0] - 1]][1] = l[0];

		res[sum[r[0]] - sum[l[0] - 1]][2] = r[0];

		if(a[l[0]] == 2){++l[0];continue;}

		if(a[r[0]] == 2){--r[0];continue;}

		++l[0];--r[0];

	}

	for(;l[1] <= r[1];)

	{

		res[sum[r[1]] - sum[l[1] - 1]][1] = l[1];

		res[sum[r[1]] - sum[l[1] - 1]][2] = r[1];

		if(a[l[1]] == 2){++l[1];continue;}

		if(a[r[1]] == 2){--r[1];continue;}

		++l[1];--r[1];

	}

	int k;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&k);

		if(k <= 2 * n && res[k][1] != 0)printf("%d %d\n",res[k][1],res[k][2]);

		else puts("NIE");

	}

	return 0;

}