連載しょぼんコーダー番外編1 平方分割を実装してみた

バグループ

聴いてください、バグループ
バグってない平方分割を知らない
バグってない平方分割が実装できない
バグってない平方分割を知らない
バグってない平方分割が実装できないよ

蟻本 pp169-170 を参考にして, 自分なりに平方分割を実装してみた.

Library Checker - Static RMQ Library Checker

区間最小値はセグメント木でも行けるが, 平方分割でも行ける.

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,q;
    cin >> n >> q;
    int b = int(pow(n, 0.5) + 1);
    vector<int> a(n);
    for (int i=0; i<n; i++){
        cin >> a[i];
    }

    vector<int> dat(b, 1e9);
    for (int i=0; i<b; i++){
        for (int j=min(n, i*b); j<min(n, (i+1)*b); j++){
            dat[i] = min(dat[i], a[j]);
        }
    }

    for (int num=0; num<q; num++){
        int l, r;
        cin >> l >> r;
        int tl = l+b-(l%b), tr = r-(r%b), ans = 1e9;
        for (int i=l; i<min(r,tl); i++){
            ans = min(ans, a[i]);
        }
        for (int i=tl/b; i<tr/b; i++){
            ans = min(ans, dat[i]);
        }
        for (int i=max(tl,tr); i<r; i++){
            ans = min(ans, a[i]);
        }
        cout << ans << endl;
    }
}

説明

細かくみていく.

b

int b = int(pow(n, 0.5) + 1);

bはバケットのサイズでもあるが, バケットの数でもある. +1でうまい具合に調整してある.

前処理

vector<int> dat(b, 1e9);
for (int i=0; i<b; i++){
    for (int j=min(n, i*b); j<min(n, (i+1)*b); j++){
        dat[i] = min(dat[i], a[j]);
    }
}

前処理はこんな感じ. 各バケットについて計算している. ここは $O(N)$

（追記 2022/09/03）for文だと必要ないが, sortだとバケットの左端jを i*b としてしまうと配列外にアクセスしてしまう. これを防ぐために, ここの時点で for int j min(n, i*b) と書いている.

RMQ

for (int num=0; num<q; num++){
    int l, r;
    cin >> l >> r;
    int tl = l+b-(l%b), tr = r-(r%b), ans = 1e9;

    // (1)
    for (int i=l; i<min(r,tl); i++){
        ans = min(ans, a[i]);
    }

    // (2)
    for (int i=tl/b; i<tr/b; i++){
        ans = min(ans, dat[i]);
    }

    // (3)
    for (int i=max(tl,tr); i<r; i++){
        ans = min(ans, a[i]);
    }
    
    cout << ans << endl;
}