Mo′s Algorithm(クエリ平方分割)について

はじめに

区間計算を行う際に累積和やSegment Treeを用いがちですが、それでは上手くいかない問題もあります。
そのような問題の一部を解く手法としてMo′s Algorithmがあります。
次にMo′s Algorithmが使える問題の例を挙げます。

問題

$${N}$$個の数$${A_0……A_{N-1}}$$があります。
次の$${Q}$$個のクエリに答えてください。
「$${l,r}$$が与えられるので$${A_l……A_r}$$に含まれる値の種類数を答えよ」

制約

$${1\le N\le10^5}$$
$${1\le Q\le10^6}$$
$${1\le A_i \le N}$$
各クエリについて$${1\le l\le r \le N}$$

厳しい世界

雑に全探索とかをやるとすぐに$${O(QN)}$$になって死んでしまいます。

追加の制約

$${n=\min(100,N)}$$
$${1\le l \le n}$$
つまり左端は高々$${100}$$までという制約を追加します。

右端がボトルネックに

毎回区間計算するとどうしても$${O(QN)}$$になってしまう。
$${O(Qn)}$$なら通るんだけどなぁ……。
ということで頑張りましょう。
しゃく取り法の要領で区間を伸び縮みさせて解くことを考えます。
左端は毎回$${O(n)}$$かかり、全体で$${O(Qn)}$$。
通りますねぇ。
右端は毎回$${O(N)}$$かかり、全体で$${O(QN)}$$。
通りませんねぇ。
どうにか右端の処理を高速化したい。
ということで、右端の値でクエリをソートします。
これによって右端も毎回伸び縮みしていたのが伸び続ける(小さい順ソートの場合)、縮み続ける(大きい順ソートの場合)のどちらかになります。
右端についての全体的な計算量が$${O(N)}$$となり、これによって左端右端合わせての計算量が$${O(Qn+N)}$$に落ち、通ります。

左端はバラバラだが取る範囲が狭いため計算量が少なくて済む($${O(Qn)}$$)
右端は取る範囲が広い代わりにソートされていて計算量が少なくて済む($${O(N)}$$)

元の制約も弱い制約の繰り返しで解ける

自分で勝手に$${n}$$を定めて左端の位置を$${n}$$で割った値でクエリを分けてしまいましょう。
これによって追加の制約の問題が複数ある状態に帰着します。
この時の計算量は$${O(Qn+N(\frac{N}{n}))}$$となります。
左端によって$${\frac{N}{n}}$$個の問題に分解しているので右端の$${O(N)}$$操作を$${\frac{N}{n}}$$回やることになりこのような計算量になります。

nの決め方

適当に決め……てはダメです。
$${n=N}$$にしたら左端の計算量が$${O(QN)}$$になりますし、$${n=1}$$にしたら右端の計算量が$${O(N^2)}$$になります。
$${n=\frac{N}{\sqrt Q}}$$くらいが丁度いいです。
というのも左端の計算量が$${O(N \sqrt  Q)}$$、右端の計算量も$${O(N \sqrt  Q)}$$になるからです。

コード

ソートを分割したブロックの偶奇によって反転させているのは定数倍高速化のためです。

#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

//クエリ平方分割 0-indexed,半開区間
//入力データの型(今回はlong long int)と答えの型(今回はlong long int)
template<typename T,typename ResultT>
class MoAlgorithm{
    public:
    long long int data_size_;
    long long int query_size_;
    long long int threshold_;//閾値
    long long int division_num_;//分割した数

    //ここを変更
    long long int restmp_;//内部で保管するデータ
    vector<long long int>cou_;//各種類の個数をメモする配列

    vector<T>data_;
    vector<pair<long long int,long long int>>query_;
    vector<vector<pair<pair<long long int,long long int>,long long int>>>divided_query_;
    vector<ResultT>res_;
    MoAlgorithm(vector<T>input_data_,vector<pair<long long int,long long int>>input_query_):data_(input_data_),query_(input_query_){
        data_size_=data_.size();
        query_size_=query_.size();
        division_num_=max(1LL,(long long int)sqrt(data_size_));//ルートQくらい
        threshold_=1+(data_size_-1)/division_num_;//N/ルートQくらい
        
        //クエリを分割(sortしやすいようにl,rを反転)
        divided_query_=vector<vector<pair<pair<long long int,long long int>,long long int>>>(division_num_);
        for(long long int i_=0;i_<query_size_;i_++){
            divided_query_[query_[i_].first/threshold_].push_back({{query_[i_].second,query_[i_].first},i_});
        }
        //分割した部分ごとに右辺をソートし反転を元に戻す
        for(long long int i_=0;i_<division_num_;i_++){
            if(i_%2==0)sort(divided_query_[i_].begin(),divided_query_[i_].end());
            else sort(divided_query_[i_].begin(),divided_query_[i_].end(),greater<pair<pair<long long int,long long int>,long long int>>());
            for(long long int j_=0;j_<divided_query_[i_].size();j_++){
                swap(divided_query_[i_][j_].first.first,divided_query_[i_][j_].first.second);
            }
        }
        long long int l_=0,r_=0;
        ResClear();
        Clear();
        //分割されたブロック毎の処理
        for(long long int i_=0;i_<division_num_;i_++){
            for(long long int j_=0;j_<divided_query_[i_].size();j_++){
                while(l_<divided_query_[i_][j_].first.first){
                    DeleteData(l_);
                    l_++;
                }
                while(l_>divided_query_[i_][j_].first.first){
                    InsertData(l_-1);
                    l_--;
                }
                while(r_<divided_query_[i_][j_].first.second){
                    InsertData(r_);
                    r_++;
                }
                while(r_>divided_query_[i_][j_].first.second){
                    DeleteData(r_-1);
                    r_--;
                }
                res_[divided_query_[i_][j_].second]=Calc();
            }
        }
        
    }
    //解答データ初期化
    void ResClear(){
        res_=vector<ResultT>(query_size_,0);
    }
    //内部データ初期化
    void Clear(){
        restmp_=0;
        cou_=vector<long long int>(data_size_);
    }
    //データ追加
    void InsertData(long long int id_){
        if(cou_[data_[id_]]==0)restmp_++;
        cou_[data_[id_]]++;
    }
    //データ削除
    void DeleteData(long long int id_){
        cou_[data_[id_]]--;        
        if(cou_[data_[id_]]==0)restmp_--;
    }
    ResultT Calc(){
        //現在のinternal_data_から答えを計算
        return restmp_;
    }
};


long long int N,Q;

int main() {
    cin>>N;
    vector<long long int>A(N);
    for (long long int i = 0; i < N; i++)
    {
        cin>>A[i];
        A[i]--;
    }
    cin>>Q;
    vector<pair<long long int,long long int>>lr(Q);
    for (long long int i = 0; i < Q; i++)
    {
        cin>>lr[i].first>>lr[i].second;
        lr[i].first--;
    }
    MoAlgorithm<long long int,long long int> MA(A,lr);
    for (long long int i = 0; i < Q; i++)
    {
        cout<<MA.res_[i]<<endl;
    }
    
}

参考にさせていただいたサイト

https://ei1333.hateblo.jp/entry/2017/09/11/211011