BOJ 22959 - 신촌 수열과 쿼리

BOJ 22959 - 신촌 수열과 쿼리

뻔한 세그먼트 트리 문제이다.

문제를 잘 읽어보면 2번 쿼리에서 항상 $i$ 는 구간에 포함이 되어있어야 하는데, 그럼 $i$ 를기준으로 왼쪽으로 얼마나 $j$ 이상인 것이 긴지, 오른쪽으론 얼마나 긴지를 세그먼트 트리로 $O(\log ^2n)$ 혹은 $O(\log n)$ 으로 구할 수 있다.

다음과 같은 코드는 그냥 이분탐색으로 $O(\log ^2n)$ 으로 푼 것으로 시간안에 통과한다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   seg_tree<int> seg(n);
   for (int i = 0; i < n; i++) seg.update(i, a[i]);
   int q;
   cin >> q;
   while (q--) {
      int c, i, j;
      cin >> c >> i >> j;
      i--;
      if (c == 1) {
         seg.update(i, j);
      } else {
         int lo = 0, hi = i, ret = i;
         while (lo <= hi) {
            int m = lo + hi >> 1;
            if (seg.query(m, i).min >= j) ret = m, hi = m - 1;
            else lo = m + 1;
         }
         int leftmost = ret;
         lo = i, hi = n - 1, ret = i;
         while (lo <= hi) {
            int m = lo + hi >> 1;
            if (seg.query(i, m).min >= j) ret = m, lo = m + 1;
            else hi = m - 1;
         }
         int rightmost = ret;
         cout << seg.query(leftmost, rightmost).sum << endl;
      }
   }
}