BOJ 28140 - 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕!

BOJ 28140 - 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕!

R, B의 위치들에 대해 이분탐색해 $O(N+Q\log N)$ 에 풀 수도 있고, 적절히 전처리해 $O(N + Q)$ 에 풀 수도 있다.

void solve() {
   int n, q;
   cin >> n >> q;
   string s;
   cin >> s;

   vi R, B;
   for (int i = 0; i < n; i++) {
      if (s[i] == 'R') R.pb(i);
      if (s[i] == 'B') B.pb(i);
   }
   while (q--) {
      int l, r;
      cin >> l >> r;

      vi ans(4);
      int idx = lbi(R, l) + 1;
      if (idx >= sz(R) || R[idx] > r) {
         cout << -1 << endl;
         continue;
      }
      ans[0] = R[idx - 1];
      ans[1] = R[idx];

      idx = ans[1] + 1;

      idx = lbi(B, idx) + 1;
      if (idx >= sz(B) || B[idx] > r) {
         cout << -1 << endl;
         continue;
      }
      ans[2] = B[idx - 1];
      ans[3] = B[idx];

      for (int i = 0; i < 4; i++) cout << ans[i] << ' ';
      cout << endl;
   }
}