Mo's Algorithm
(Algorithm/mo.hpp)

• View this file on GitHub
• Last update: 2022-12-27 02:24:35+09:00
• Include: #include "Algorithm/mo.hpp"

使い方

Mo(int n): 要素数 $n$ のデータ構造を作成。
void add(int L,int R): 半開区間 $[L,R)$ をクエリに追加。
void run(): クエリを実行。

• addl(int i) (左側に要素 $i$ を追加)
• addr(int i) (右側に要素 $i$ を追加)
• dell(int i) (左側の要素 $i$ を削除)
• delr(int i) (右側の要素 $i$ を削除)
• out(int i) (クエリ $i$ の結果を書き込む)
  を準備する必要がある。

Verified with

• Verify/LC_static_range_inversions_query.test.cpp

Code

#pragma once

struct Mo{
    const int n;
    vector<int> L,R;
    Mo(int _n):n(_n){}
    void add(int lb,int rb){
        L.push_back(lb);
        R.push_back(rb);
    }
    template <typename AL, typename AR, typename DL, typename DR, typename OUT>
    void run(const AL& addl,const AR& addr,const DL& dell,const DR& delr,const OUT& out){
        const int q=L.size();
        const int w=max<int>(1,1.0*n/max<double>(1.0,sqrt(q*2.0/3.0)));
        vector<int> ord(q);
        iota(ALL(ord),0);
        sort(ALL(ord),[&](int i,int j){
            int a=L[i]/w,b=L[j]/w;
            if(a!=b)return a<b;
            if(a&1)return R[i]<R[j];
            else return R[i]>R[j];
        });
        int lb=0,rb=0;
        for(auto& i:ord){
            while(lb>L[i])addl(--lb);
            while(rb<R[i])addr(rb++);
            while(lb<L[i])dell(lb++);
            while(rb>R[i])delr(--rb);
            out(i);
        }
    }
};

/**
 * @brief Mo's Algorithm
 * @docs docs/mo.md
 */

#line 2 "Algorithm/mo.hpp"

struct Mo{
    const int n;
    vector<int> L,R;
    Mo(int _n):n(_n){}
    void add(int lb,int rb){
        L.push_back(lb);
        R.push_back(rb);
    }
    template <typename AL, typename AR, typename DL, typename DR, typename OUT>
    void run(const AL& addl,const AR& addr,const DL& dell,const DR& delr,const OUT& out){
        const int q=L.size();
        const int w=max<int>(1,1.0*n/max<double>(1.0,sqrt(q*2.0/3.0)));
        vector<int> ord(q);
        iota(ALL(ord),0);
        sort(ALL(ord),[&](int i,int j){
            int a=L[i]/w,b=L[j]/w;
            if(a!=b)return a<b;
            if(a&1)return R[i]<R[j];
            else return R[i]>R[j];
        });
        int lb=0,rb=0;
        for(auto& i:ord){
            while(lb>L[i])addl(--lb);
            while(rb<R[i])addr(rb++);
            while(lb<L[i])dell(lb++);
            while(rb>R[i])delr(--rb);
            out(i);
        }
    }
};

/**
 * @brief Mo's Algorithm
 * @docs docs/mo.md
 */

Back to top page