BOJ 24547 - mod와 쿼리 (D4)

사용 알고리즘

Segment Tree, Sqrt Decomposition, Number Theory(Harmonic Lemma)

 

풀이

쿼리 1번은 잘못 보면 그냥 단순한 합 문제로 보이지만, 시그마 안에 mod가 있어서 단순한 문제는 아니라는 걸 알 수 있다. (이 사실을 코드 짜고 예제 1번 돌려보기 전까지 몰랐다.)

하지만 그렇게 어려운 문제도 아니다(?). X의 범위에 따라 나눠서 처리하면 되는데, X <= 316(약 sqrt(10^5))일때는 3번 쿼리에서 배열에다 일일히 합 mod X를 업데이트해두고 O(1)에 처리하면 된다. X > 316일때는 크기 X칸의 버킷에 따라 mod X할 때 빼야하는 X의 개수가 다르다는 점을 이용해 O(10^5/X)에 처리할 수 있다.

 

쿼리 2번은 좀 더 복잡하다. 일단 mod의 정의를 이용해 단순화해보면 이 쿼리는 \(  nX - \sum A_{i} * \left \lfloor \frac{X}{A_{i}}\right \rfloor \)를 구하는 문제다. 여기서 floor 부분을 주목하면, harmonic lemma 형태임을 알 수 있다. 따라서 O(sqrt(10^5)) 정도에 저 floor가 같은 것끼리 세그먼트 트리로 묶어서 계산해줄 수 있고 쿼리당 O(sqrt(10^5)*logN) 정도가 걸린다.

 

쿼리 3번은 업데이트만 해주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll n, q;
struct fenwick{
    vector<ll> tree;
    fenwick(): tree(101010) {}
    void upd(ll i, ll x){
        while(i<=100000)tree[i] += x, i += (i&-i);
    }
    ll sum(ll i, ll ret=0){ while(i>0)ret += tree[i], i -= (i&-i); return ret; }
    ll query(ll l, ll r){ if(l>r)return 0; return sum(min<ll>(100000,r)) - sum(l-1); }
} seg, cnt;
ll A[101010];
ll cur[333];
int main(){
    fast;
    cin>>n;
    for(int i = 1 ; i <= n ; i++){
        cin>>A[i];
        seg.upd(A[i],A[i]);
        cnt.upd(A[i],1);
        for(int j = 1 ; j <= 316 ; j++)cur[j] += A[i]%j;
    }
    cin>>q;
    while(q--){
        ll op,a,b; cin>>op>>a;
        if(op==1){
            ll ans = seg.query(1,100000);
            if(a>316){
                for(int i = 0, j = 0 ; i <= 100000 ; i += a, j++){
                    ans -= a * j * cnt.query(i,i+a-1);
                }
            }
            else{
                ans = cur[a];
            }
            cout<<ans<<"\n";
        } if(op==2){
            ll ans = n * a;
            for(int i = 1,j = 1 ; i <= a ; i=j+1){
                j = (a/(a/i));
                ans -= (a/i) * seg.query(i,j);
            }
            cout<<ans<<"\n";
        } if(op==3){
            cin>>b;
            seg.upd(A[a],-A[a]);
            cnt.upd(A[a],-1);
            for(int j = 1 ; j <= 316 ; j++)cur[j] -= A[a]%j;
            A[a] = b;
            for(int j = 1 ; j <= 316 ; j++)cur[j] += A[a]%j;
            cnt.upd(A[a],1);
            seg.upd(A[a],A[a]);
        }
    }
}

쿼리 1번은 이 문제와 아이디어가 유사하다.