BOJ 17410 : 수열과 쿼리 1.5

• 문제 링크 : boj.kr/17410
• 난이도 : D5
• 태그 : 제곱근 분할법, 누적합

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> arr(n);
    for(auto &e : arr) cin >> e;
    int s = sqrt(n);
    vector<array<int, 10001>> bucket(n/s+1);
    for(int i = 0; i < n; i++) {
        bucket[i/s][arr[i]]++;
    }
    for(int i = 1; i < bucket.size(); i++) {
        for(int j = 0; j <= 10000; j++) {
            bucket[i][j] += bucket[i-1][j];
        }
    }

    int m;
    cin >> m;
    for(int i = 0; i < m; i++) {
        int q;
        cin >> q;
        if(q == 1) {
            int idx, v;
            cin >> idx >> v;
            idx--;
            for(int i = idx / s; i < bucket.size(); i++) {
                bucket[i][arr[idx]]--;
                bucket[i][v]++;
            }
            arr[idx] = v;
        }
        if(q == 2) {
            int i, j, k;
            cin >> i >> j >> k;
            i--, j--;
            int ix = i/s, jx = j/s;
            int ans = 0;
            for(int t = k+1; t <= 10000; t++) {
                int r = bucket[jx][t];
                int l = (ix > 0) ? bucket[ix-1][t] : 0;
                ans += r-l;
            }
            for(int t = ix*s; t < i; t++) {
                ans -= (arr[t] > k);
            }
            for(int t = j+1; t < min(jx*s+s, n); t++) {
                ans -= (arr[t] > k);
            }
            cout << ans << "\n";
        }
    }


    return 0;
}

---

풀이

#14504와 비슷한 문제이지만, 시간제한이 더 작고, 수의 범위도 작다.

수의 범위가 작기 때문에 각 버킷에 있는 수의 개수를 세어 저장할 수 있다.

이제 남은 것은 한 버킷부터 다른 버킷 사이에 있는 어떤 수를 $O(1)$로 세는 것이다.

누적합을 이용해주면 $O(1)$로 셀 수 있고, 따라서 2번 쿼리의 경우 $O(\sqrt N+10000)$으로 처리할 수 있다.

1번 쿼리의 경우 누적합을 업데이트 하는 것이므로 $O(\sqrt N)$으로 처리할 수 있다.