抽象ヒルベルトMo'sライブラリ

　難問でときどき必要になりますよね。

　ヒルベルト曲線だと定数倍がよくなるそうなので実装します、AIが。

　コンテスト中にすると不正になってしまうので、それ以外の時間である今まとめます。

struct HilbertMo {
    struct Query {
        int l, r, idx;
        ll ord;
    };

    vector<Query> qs;

    static ll hilbert_order(int x, int y, int pow = 21, int rotate = 0) {
        if(pow == 0) return 0;
        int hpow = 1 << (pow - 1);
        int seg = (x < hpow ?
                  (y < hpow ? 0 : 3) :
                  (y < hpow ? 1 : 2));
        seg = (seg + rotate) & 3;
        static const int rotate_delta[4] = {3, 0, 0, 1};
        int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
        int nrot = (rotate + rotate_delta[seg]) & 3;
        ll sub_square_size = 1LL << (2 * pow - 2);
        ll ans = seg * sub_square_size;
        ll add = hilbert_order(nx, ny, pow - 1, nrot);
        ans += (seg == 1 || seg == 2) ? add : (sub_square_size - add - 1);
        return ans;
    }

    void add_query(int l, int r, int idx) {
        qs.push_back({l, r, idx, hilbert_order(l, r)});
    }

    template<class AL, class AR, class EL, class ER, class OUT>
    void run(AL add_left, AR add_right, EL erase_left, ER erase_right, OUT out) {
        sort(qs.begin(), qs.end(), [](const Query& a, const Query& b) {
            return a.ord < b.ord;
        });

        int l = 0, r = 0;
        for(auto [ql, qr, idx, ord] : qs) {
            while(l > ql) add_left(--l);
            while(r < qr) add_right(r++);
            while(l < ql) erase_left(l++);
            while(r > qr) erase_right(--r);
            out(idx);
        }
    }
};

使い方

作成

• HilbertMo コンストラクタです。とくに引数は必要ないです

クエリ追加

• add_query で区間を追加していきます。0-idx です。ソートは必要ないです

関数定義

• add_left left が増えるとき、つまり左にいくときの処理です
• add_right right が増えるとき、つまり右にいくときの処理です
• erase_left left が減るとき、つまり右にいくときの処理です
• erase_right right が減るとき、つまり左にいくときの処理です
• out その段階での値をメモします

実行

• run クエリを実行します

使用例

　単純な累積和ですが、あえて Mo's でときます。

int main(){
    int n;
    cin >> n;
    int q;
    cin >> q;
    vector<int> a(n);
    cin >> a;
    HilbertMo mo;
    rep(i,q){
        int L,R;
        cin >> L >> R;
        L--;
        mo.add_query(L,R,i);
    }
    vector<ll> ans(q);
    ll now = 0;
    auto L_add=[&](int i){
        now += a[i];
    };
    auto R_add=[&](int i){
        now += a[i];
    };
    auto L_erase=[&](int i){
        now -= a[i];
    };
    auto R_erase=[&](int i){
        now -= a[i];
    };
    auto out=[&](int i){
        ans[i] = now;
    };
    mo.run(L_add,R_add,L_erase,R_erase,out);
    for(ll i:ans){
        cout << i << endl;
    }
}