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;
}