P3514

题目传送门

这是一个稍微复杂一点且较容易想到的做法。

考虑 特殊到一般，我们固定一个右端点 $l$，枚举左端点 $r$，将 $[l,r]$ 算入答案。这样显然会漏掉一些答案，发现必然是进行 $+2$ 时跳过了一个数，考虑如何得到这个数。

发现如果 $a_l=1$，我们将 $l\leftarrow l+1$，则枚举左端点 $r$ 得到的数恰好对于上一次计算的数 $-1$，可以补上。那么我们找到第一个出现 $1$ 的位置也就是现在我们得到了 $[1,s_{l,n}]$ 的答案，其中 $s_{l,r}$ 表示 $\sum\limits_{i=l}^{r}a_i$ 。

考虑还要将 $[1,l-1]$ 的 $2$ 算入答案，这个我们在以 $l$ 为左端点时对计算的和 $s_{l,r}$ 记录数组 $b_{s_{l,r}}$ $l$ 前面可以拓展多少个 $2$，对于每个 $i$ 存在答案且 $b_i>0$，都可以计算出 $i+2$ 的答案，从小到大递推即可，具体见代码。

bool START;

const int N = 2e6 + 5;

int n, q, a[N], b[N];
pr ans[N];
char s[N];

bool END;

void cl(int l, bool fl) {
  if (fl) b[0] = l - 1;
  for (int i = l, sm = 0; i <= n; ++i) {
    sm += a[i], ans[sm] = mk(l, i);
    if (fl) b[sm] = l - 1;
  }
}

void cl2() {
  for (int i = 0; i <= 2 * n; ++i)
    if (ans[i] != mk(0, 0) && b[i] > 0 && (ans[i + 2] == mk(0, 0) || b[i + 2] < b[i] - 1))
      b[i + 2] = b[i] - 1, ans[i + 2] = ans[i], ans[i + 2].fi--;
}

signed main() {
  IN(n), IN(q), scanf(" %s", s + 1); for (int i = 1; i <= n; ++i) a[i] = (s[i] == 'T') ? 2 : 1;
  int p = n + 1;
  for (int i = 1; i <= n; ++i) if (a[i] == 1) {p = i; break;}
  cl(p + 1, 0), cl(p, 1),  ans[0] = mk(p, p - 1), cl2();
  while (q--) {
    int x; IN(x);
    if (ans[x] == mk(0, 0)) puts("NIE");
    else cout << ans[x].fi << ' ' << ans[x].se << endl;
  }
  return 0;
}