icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: 木上の Mo
(tree/Mo_on_Tree.hpp)

木上の Mo

木上のMoは、木上のパスクエリを Euler Tour 順に頂点あるいは辺を並べてその列上での区間クエリとして解釈する。

木を頂点 $0$ の根付き木とし、 $\mathrm{par}(v)$ を $v$ の親とする。ただし $v=0$ のときは $-1$ とする。頂点 $0$ から Euler Tour をし、通った辺とその重みを順に並べた配列 vals を作る。また、初めて頂点 $v$ を訪れた時刻　in[v] を記録する。ここで、パスクエリ $(u,v)$ は vals 上で [in[u],in[v]) へのクエリに対応する。その区間で辺 $i$ が含まれている個数を $c(i)$ 個とすると、パス上で辺 $i$ は $(c(i)\bmod 2)$ 個含まれている。木上のMoはパスに含まれる辺の順序を考慮せず、含まれる辺は集合として扱われる。つまり、通常のMoが要求する add_left, add_right, del_left, del_right は辺の集合への追加 add および削除 del に置き換えられる。ここで注意したいことは、通常のMoでは区間を収縮する関数はそのindexを引数に取るが、この木上のMoのライブラリが要求する add, del は重みそのものを引数に取る。また、ライブラリ内部で辺が今集合に含まれているかを表す contain を管理している。内部では区間の収縮の際に集合に辺を追加するか削除するかを切り替えられるように change を定義し、それを通常のMoに投げている。

さて、辺に重みがついている場合と異なり、頂点に重みがついている場合は工夫が必要である。頂点に重みがついている場合は、$v$ の重みを $\mathrm{par}(v)$ への辺に乗せる。また、パスクエリ $(u,v)$ は vals[in[u],in[v]) $\cup \lbrace$ 頂点 $\mathrm{lca}(u,v)$ の重み $\rbrace$ が表す集合へのクエリと解釈する。$(u,v)$ クエリを投げる際には insert(u,v,lca) として、$\mathrm{lca}(u,v)$ を要求する。

Depends on

Verified with

Code

#pragma once

#include"../template/template.hpp"
#include"../misc/mo_algorithm.hpp"

/*

MoTree_edge is verified with : https://atcoder.jp/contests/pakencamp-2022-day1/submissions/43052952

*/

namespace lib{

template<class T>
struct MoTree_edge {
    int n;
    vector<vector<pair<int,T>>> es;
    MoTree_edge (int _n) : n(_n) {
        es.resize(n);
    }
    void add_edge(int u, int v, T w){
        es[u].emplace_back(v,w);
        es[v].emplace_back(u,w);
    }
    vector<int> in;
    vector<pair<int,T>> vals;
    Mo mo;
    void build(int q){
        int tnow = 0;
        auto dfs = [&](auto dfs, int v, int f) -> void {
            in[v] = tnow++;
            for (auto [u, w] : es[v]){
                if (u == f) continue;
                vals.emplace_back(u,w);
                dfs(dfs,u,v);
                vals.emplace_back(u,w);
                tnow++;
            }
        };
        in.resize(n);
        dfs(dfs,0,-1);
        mo = Mo(2*n-2,q);
    }
    void insert(int u, int v){
        u = in[u], v = in[v];
        if (u > v) swap(u,v);
        mo.insert(u,v);
    }
    template<typename ADD, typename DEL, typename REM>
    void run(const ADD &add, const DEL &del, const REM &rem){
        vector<bool> contain(n,false);
        auto change = [&](int i){
            int id = vals[i].first;
            if (contain[id]){
                del(vals[i].second);
                contain[id] = false;
            }
            else {
                add(vals[i].second);
                contain[id] = true;
            }
        };
        mo.run(change,change,change,change,rem);
    }
};


template<class T>
struct MoTree_vertex {
    int n;
    vector<vector<int>> es;
    vector<T> b;
    MoTree_vertex (int _n, vector<T> _b) : n(_n), b(_b) {
        es.resize(n);
    }
    void add_edge(int u, int v){
        es[u].emplace_back(v);
        es[v].emplace_back(u);
    }
    vector<int> in;
    vector<pair<int,T>> vals;
    vector<int> lcas;
    Mo mo;
    void build(int q){
        vals.reserve(2*n-2);
        lcas.reserve(q);
        int tnow = 0;
        auto dfs = [&](auto dfs, int v, int f) -> void {
            in[v] = tnow++;
            for (auto u : es[v]){
                if (u == f) continue;
                vals.emplace_back(u,b[u]);
                dfs(dfs,u,v);
                vals.emplace_back(u,b[u]);
                tnow++;
            }
        };
        in.resize(n);
        dfs(dfs,0,-1);
        mo = Mo(2*n-2,q);
    }
    
    void insert(int u, int v, int lca){
        u = in[u], v = in[v];
        if (u > v) swap(u,v);
        mo.insert(u,v);
        lcas.push_back(lca);
    }
    template<typename ADD, typename DEL, typename REM>
    void run(const ADD &add, const DEL &del, const REM &rem){
        vector<bool> contain(n,false);
        auto change = [&](int i){
            int id = vals[i].first;
            if (contain[id]){
                del(vals[i].second);
                contain[id] = false;
            }
            else {
                add(vals[i].second);
                contain[id] = true;
            }
        };
        auto rem_add_lca = [&](int i){
            add(b[lcas[i]]);
            rem(i);
            del(b[lcas[i]]);
        };
        mo.run(change,change,change,change,rem_add_lca);
    }
};

} // namespace lib
#line 2 "tree/Mo_on_Tree.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 2 "misc/mo_algorithm.hpp"

#line 4 "misc/mo_algorithm.hpp"

namespace lib {

struct Mo {
    int width;
    vector<int> left, right, order;

    Mo(int N = 1, int Q = 1) : order(Q) {
        width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
        iota(begin(order), end(order), 0);
    }

    void insert(int l, int r) { /* [l, r) */
        left.emplace_back(l);
        right.emplace_back(r);
    }

    template <typename AL, typename AR, typename DL, typename DR, typename REM>
    void run(const AL &add_left, const AR &add_right, const DL &delete_left,
             const DR &delete_right, const REM &rem) {
        assert(left.size() == order.size());
        sort(begin(order), end(order), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            if (ablock & 1) return right[a] < right[b];
            return right[a] > right[b];
        });
        int nl = 0, nr = 0;
        for (auto idx : order) {
            while (nl > left[idx]) add_left(--nl);
            while (nr < right[idx]) add_right(nr++);
            while (nl < left[idx]) delete_left(nl++);
            while (nr > right[idx]) delete_right(--nr);
            rem(idx);
        }
    }
};

}  // namespace lib
#line 5 "tree/Mo_on_Tree.hpp"

/*

MoTree_edge is verified with : https://atcoder.jp/contests/pakencamp-2022-day1/submissions/43052952

*/

namespace lib{

template<class T>
struct MoTree_edge {
    int n;
    vector<vector<pair<int,T>>> es;
    MoTree_edge (int _n) : n(_n) {
        es.resize(n);
    }
    void add_edge(int u, int v, T w){
        es[u].emplace_back(v,w);
        es[v].emplace_back(u,w);
    }
    vector<int> in;
    vector<pair<int,T>> vals;
    Mo mo;
    void build(int q){
        int tnow = 0;
        auto dfs = [&](auto dfs, int v, int f) -> void {
            in[v] = tnow++;
            for (auto [u, w] : es[v]){
                if (u == f) continue;
                vals.emplace_back(u,w);
                dfs(dfs,u,v);
                vals.emplace_back(u,w);
                tnow++;
            }
        };
        in.resize(n);
        dfs(dfs,0,-1);
        mo = Mo(2*n-2,q);
    }
    void insert(int u, int v){
        u = in[u], v = in[v];
        if (u > v) swap(u,v);
        mo.insert(u,v);
    }
    template<typename ADD, typename DEL, typename REM>
    void run(const ADD &add, const DEL &del, const REM &rem){
        vector<bool> contain(n,false);
        auto change = [&](int i){
            int id = vals[i].first;
            if (contain[id]){
                del(vals[i].second);
                contain[id] = false;
            }
            else {
                add(vals[i].second);
                contain[id] = true;
            }
        };
        mo.run(change,change,change,change,rem);
    }
};


template<class T>
struct MoTree_vertex {
    int n;
    vector<vector<int>> es;
    vector<T> b;
    MoTree_vertex (int _n, vector<T> _b) : n(_n), b(_b) {
        es.resize(n);
    }
    void add_edge(int u, int v){
        es[u].emplace_back(v);
        es[v].emplace_back(u);
    }
    vector<int> in;
    vector<pair<int,T>> vals;
    vector<int> lcas;
    Mo mo;
    void build(int q){
        vals.reserve(2*n-2);
        lcas.reserve(q);
        int tnow = 0;
        auto dfs = [&](auto dfs, int v, int f) -> void {
            in[v] = tnow++;
            for (auto u : es[v]){
                if (u == f) continue;
                vals.emplace_back(u,b[u]);
                dfs(dfs,u,v);
                vals.emplace_back(u,b[u]);
                tnow++;
            }
        };
        in.resize(n);
        dfs(dfs,0,-1);
        mo = Mo(2*n-2,q);
    }
    
    void insert(int u, int v, int lca){
        u = in[u], v = in[v];
        if (u > v) swap(u,v);
        mo.insert(u,v);
        lcas.push_back(lca);
    }
    template<typename ADD, typename DEL, typename REM>
    void run(const ADD &add, const DEL &del, const REM &rem){
        vector<bool> contain(n,false);
        auto change = [&](int i){
            int id = vals[i].first;
            if (contain[id]){
                del(vals[i].second);
                contain[id] = false;
            }
            else {
                add(vals[i].second);
                contain[id] = true;
            }
        };
        auto rem_add_lca = [&](int i){
            add(b[lcas[i]]);
            rem(i);
            del(b[lcas[i]]);
        };
        mo.run(change,change,change,change,rem_add_lca);
    }
};

} // namespace lib
Back to top page