BOJ 17410 수열과 쿼리 1.5

Solved.ac 난이도 기준 플5 이상 문제를 하루 하나씩 풀어보려고 시작했다. (시험기간엔 못 하겠지만...)

 

(사실 플레는 아니고, 푼 시점에서는 다4로 되어 있었다.)

 

문제설명

$n$개짜리 수열에 대해 두가지 쿼리를 합하여 $q$개 처리해야 한다. ($n \leq 1e5, q \leq 2e5$)

1 $i$ $v$ 쿼리 : $A_i$ 를 $v$로 바꾼다.

2 $i$ $j$ $k$ 쿼리 : $A_i$ 부터 $A_j$ 까지의 Subsegment에서, $k$보다 큰 원소의 개수를 센다.

---

풀이

Naive하게 모두 센다면, 2번 쿼리 하나를 처리하는데 $O(n)$ 시간이 걸려서 $O(qn)$ 이 된다. 즉, 핵심은 2번 쿼리를 얼마나 빠르게 답할 수 있는가에 달려 있음을 알 수 있다.

Sqrt decomposition을 사용하자 (이름이 이렇긴 하지만, 실제로는 약간의 디테일이 있다)

전체 10만개짜리 배열을 적당히 $u = \sqrt{n}$ 개씩 쪼개어 저장해 둔다. 10만의 제곱근은 대략 300이 조금 넘고, 굳이 정확할 필요는 없으니 330개짜리 벡터 330개로 나눈다고 생각하자. 하나하나를 버킷이라고 보통 많이 부른다.

즉, 0번 벡터는 0~329, 1번 벡터는 330~659번 원소들을 '정렬된 상태' 로 가지고 있는다.

 

이때, 1번 쿼리가 들어오면 다음과 같이 진행한다.

- 먼저 몇번 벡터에 해당하는 인덱스인지를 확인하고.

- 해당 벡터에서 바뀌기 전 $A_i$ 값을 erase한 다음

- 벡터에 바뀐 후 $A_i$ 값을 '정렬성을 유지하면서' insert 한다.

 

시간을 분석해 보면, 먼저 몇번 버킷(벡터) 인지 찾는것은 당연히 나눗셈 한번, erase에 드는 시간은 원소를 찾는 시간 + delete 하는 시간인데 찾는 시간은 정렬된 벡터에서 찾을 것이므로 $\log{u}$ ($u$ 는 버킷의 크기), delete 시간은 vector delete가 size만큼 걸리므로 $u$ 정도 시간이 든다. insert도 자리 찾는데 $\log{u}$, 실제 삽입에 $u$ 정도 시간이 든다. 종합해서 대충 $u$ 정도 시간이 드는 셈이다.

 

2번 쿼리가 들어오면, 크게 세 구간으로 나눈다.

- $[i, j]$ 구간에 버킷 전체가 들어오는 경우 : 버킷에서 upper bound를 이용하면 $k$보다 큰 원소의 개수를 쉽게 셀 수 있다.

- 버킷이 아예 안 들어오는 경우 : 제낀다.

- 버킷에 걸쳐서 들어오는 경우 : 직접 하나씩 돌려서 $k$보다 큰 원소의 개수를 센다.

 

첫번째 경우, 버킷 최대 $n/u$ 개가 세진다. 이때 각 버킷에 upperbound 연산을 하는 시간을 생각하면 $\log{u}$ 정도 걸릴 것이다.

두번째 경우는 버킷 최대 $n/u$ 개를 보면 된다.

세번째 경우는, 생각해 보면 한 버킷을 온전히 포함하지 않으면서 양쪽에 남을 수 있는 부분의 길이는 최대 $2u$ 이다.

즉, 최악의 경우 $(n\log{u})/u$ 정도 시간이 걸린다. 

 

2번 쿼리가 많이 들어오는 경우를 생각하면 최악의 경우 시간 복잡도는 $O((n\log{u}) / u)$ 이다. 즉, $u$를 $\sqrt{n}$ 정도 잡으면 $O(\sqrt{n}\log{\sqrt{n}})$ 정도에 한 쿼리를 처리할 수 있음을 의미하며, 이는 시간에 잘 들어오는 숫자이다.

---

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int arr[101000];
vector <int> bucket[42];
int bsize;
int n, q;
int main()
{
    usecppio
    cin >> n;
    bsize = 2500;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        bucket[i/bsize].push_back(arr[i]);
    }
    for (int i = 0; i<42; i++)
        sort(all(bucket[i]));
    cin >> q;
    while (q--)
    {
        int qt;
        cin >> qt;
        if (qt == 1)
        {
            int ind, val;
            cin >> ind >> val;
            ind--;
            int u = arr[ind];
            int p = ind/bsize;
            bucket[p].erase(lower_bound(all(bucket[p]),u));
            arr[ind] = val;
            bucket[p].insert(lower_bound(all(bucket[p]),val),val);
        }
        else if (qt == 2)
        {
            int l, r, val;
            cin >> l >> r >> val;
            l--; r--;
            int lbs = l/bsize + 1 - (l%bsize==0); lbs *= bsize;
            int rbe = (r/bsize) * bsize;
            int ct = 0;
            if (lbs < rbe)
            {
                for (int i = l; i<lbs; i++)
                    if (arr[i] > val) ct++;
                for (int i = rbe; i<=r; i++)
                    if (arr[i] > val) ct++;
                int lm = lbs/bsize;
                int rm = (rbe/bsize);
                for (int i = lm; i<rm; i++)
                    ct += (bucket[i].end()- upper_bound(all(bucket[i]),val));
            }
            else
            {
                for (int i = l; i<=r; i++)
                    if (arr[i] > val) ct++;
            }

            cout << ct << '\n';
        }
    }
}

---

여담

코드를 보면, 풀이에서 설명한대로 버킷사이즈를 $\sqrt{n]$ 으로 잡지 않았다. 사실 약간의 실험이었는데,

1.5배 쯤 빨라지더라~

 

$((n\log{u}) / u)$ 의 값을 최소화하는 $u$의 값을 찾는다고 생각해 보자. 단, 1번 쿼리는 $O(u)$ 이므로, 정확히 말하면 $\max((n\log{u})/u, u)$ 를 최소화하려는 것이다.

 

첫번째 식을 미분해 보고, 대략적인 그래프의 유형을 그려 보면 $u = e$ 까지는 값이 매우 빠르게 커지고, 그 이후로는 계속 감소함수이다. 즉 한 버킷의 크기가 클수록 2번 쿼리를 빨리 처리할 수 있다. (사실 자명하다)

 

버킷의 크기가 클수록 1번 쿼리는 당연히 느려지므로, 두 쿼리의 비율이 거의 균등하다고 치면 버킷 사이즈가 $\sqrt{n}$ 보다 조금 더 커야 이득이다. 다만 실제로는 양쪽 다 상수가 붙으므로, 조금 달라지는데 어차피 이걸 요구하는 문제는 너무 :kudeki: 인거 같으므로 그냥 이런 생각도 해볼 수 있다~ 는 정도 느낌.

(어차피 상수 1.5배 차이는 저런 것보다도 캐시히트가 얼마나 잘 나는지 등등의 이슈가 더 클 수 있다)