Algorithm

Sun, Dec 12, 2021

int <-> string

to_string(int) -> string
to_string(ll) -> string
stoi(string) -> int
stoll(string) -> ll

priority queue

昇順

#include <iostream>
#include <queue>

int main() {
    // intを要素に持つ優先順位付きキュー.
    // 降順に処理する
    std::priority_queue<int> que;

    // データを追加する
    que.push(3);
    que.push(1);
    que.push(4);

    // 処理順に出力する
    while (!que.empty()) {
        std::cout << que.top() << std::endl;
        que.pop();
    }
}

4
3
1

降順に出力

#include <iostream>
#include <queue>

int main() {
    // intを要素に持つ優先順位付きキュー.
    // 降順に処理する
    std::priority_queue<int, vector<int>, greater<int>> que;

    // データを追加する
    que.push(3);
    que.push(1);
    que.push(4);

    // 降順順に出力する
    while (!que.empty()) {
        std::cout << que.top() << std::endl;
        que.pop();
    }
}

1
3
4

struct で priority queue

struct Point {
    int x, y;
};

bool operator<(const Point& a, const Point& b) {
    return a.x < b.x;
}

bool operator>(const Point& a, const Point& b) {
    return a.x > b.x;
}

void solve() {
    {
        // operator< が必要
        priority_queue<Point> pq;
        rep(i, 3) pq.push({i, 3 - i});

        while (pq.size()) {
            auto [x, y] = pq.top();
            pq.pop();
            cout << x << ' ' << y << endl;
        }
    }

    cout << endl;
    {
        // operator> が必要
        priority_queue<Point, vector<Point>, greater<Point>> pq;
        rep(i, 3) pq.push({i, 3 - i});

        while (pq.size()) {
            auto [x, y] = pq.top();
            pq.pop();
            cout << x << ' ' << y << endl;
        }
    }
}

sort

自作 struct に関して sort する.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Hoge {
    int x, y;
};

bool compare(Hoge a, Hoge b) {
    return a.y > b.y;
}

int main(int argc, char* argv[]) {
    vector<Hoge> v = {{0, 1}, {1, 9}};

    sort(v.begin(), v.end(), compare);

    for (Hoge item : v) {
        cout << item.x << " " << item.y << endl;
    }
    return 0;
}

1 9
0 1

ceil, floor

$x / y$ が負のときにも対応

// ceil(x/y)
ll ceil(ll x, ll y) {
    if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
        x = abs(x), y = abs(y);
        return (x + y - 1) / y;
    }

    // x/y が負の数のときは整数除算の x/y が切り上げになる
    return x / y;
}

// floor(x/y)
ll floor(ll x, ll y) {
    if ((x > 0 && y < 0) || (x > 0 && y < 0)) {
        if (x % y != 0)
            return x / y - 1;
    }

    return x / y;
}

未満

$s, x, P$ が正整数のとき

$$ s < \frac{P}{x} \iff s < \floor{ \frac{P+x-1}{x} } $$

が成り立つ。

$(\rightarrow)$

$$ s < \frac{P}{x} \rightarrow sx < P \rightarrow sx + 1 \leq P ~(\because s, x, P \text{ are positive integers}) $$

$f(P) = \floor{ \frac{P+x-1}{x} }$ とすると $f(P)$ は non-decreasing fn だから

$$ f(sx+1) \leq f(P) \\\\ \therefore \floor{ \frac{(sx+1)+x-1}{x} } \leq f(P) \\\\ \therefore \floor{ \frac{sx + x}{x} } \leq f(P) \\\\ \therefore \floor{ s+1 } \leq f(P) \\\\ \therefore s+1 \leq f(P) \\\\ \therefore s < s+1 \leq f(P) \\\\ \therefore s < f(P) $$

$(\leftarrow)$

$f(sx) = \floor{ \frac{sx + x-1}{x} } = \floor{ s + \frac{x-1}{x} } = s + \floor{ \frac{x-1}{x} } = s$

$f(sx+1) = s+1$

より $s < f(P)$ ならば

$$ sx+1 \leq P \\\\ \therefore sx < sx+1 \leq P \\\\ \therefore sx < P \\\\ \therefore s < \frac{P}{x} $$

ref: https://atcoder.jp/contests/abc384/tasks/abc384_e

gcd, lcm

$\mathrm{gcd}(a, b) = \mathrm{gcd}(b, a \\% b)$.

$\displaystyle \mathrm{lcm}(a,b) = \frac{a \times b}{\mathrm{gcd}(a,b)}$

Suppose $d = \mathrm{gcd}(a,b)$. This means $a = k_1 d$ and $b = k_2 d$ for some integers $k_1, k_2 \in \Z$.

$a = qb + r$ $(0 \leq r < b)$, for some integer $q$.

Then $a\\% b = r = a - qb = d(k_1 - qk_2)$.

int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

冪乗根

平方根

$x \leq \sqrt{N}$ を満たす最大の非負整数 $x$ を求める

ll isqrt(ll x) {
    // wa の最大値は x の値によって調整する
    ll ac = 0, wa = (ll)1e9 + 7;
    while (wa - ac > 1) {
        ll wj = (wa + ac) / 2;
        if (wj * wj <= x)  // 3乗根の場合は wj * wj * wj <= x にすれば良い
            ac = wj;
        else
            wa = wj;
    }

    return ac;
}

ref ABC 400 C 問題

累積和 (cumsum)

template <typename T>
vector<T> cumsum(vector<T> v) {
    int n = v.size();
    rep2(i, 1, n) v[i] += v[i - 1];
    return v;
}

3次元

詳細は ABC 366 に書いた

べき乗計算(冪乗)

高速べき乗計算

$x^n$ を高速に求める

// x^n
ll intpow(ll x, ll n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret *= x;
        x *= x;
        n >>= 1;
    }
    return ret;
}

ref: 逆元

逆元

ref: 「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜

exponential mod

// べき乗 mod
// x^n mod m
ll modpow(ll x, ll n, ll mod) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

フェルマーの小定理より素数 $p$ に対して $a^{p-1} \equiv 1 \mod p$ であるから $a^{-1} \equiv a^{p-2} \mod p$

// べき乗 inv mod
// x^{-1} mod m
ll modinv(ll x, ll mod) {
    return modpow(x, mod - 2, mod);
}

素数

エラトステネスのふるい

int MAX = 100005;
vector<int> isprime(MAX, true);
isprime[0] = isprime[1] = false;
for (int i = 2; i < MAX; i++) {
    if (isprime[i]) {
        for (int j = i + i; j < MAX; j += i) {
            isprime[j] = false;
        }
    }
}

素因数分解、約数列挙

https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/NTL_1_A/judge/10351236/C++23

// https://qiita.com/drken/items/3beb679e54266f20ab63#4-%E6%B4%BB%E7%94%A8%E4%BE%8B-1-%E9%AB%98%E9%80%9F%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E9%AB%98%E9%80%9F%E7%B4%84%E6%95%B0%E5%88%97%E6%8C%99
struct Sieve {
    vector<bool> isprime;

    // 整数 i を割り切る最小の素数
    vector<int> minfactor;

    Sieve(int N)
        : isprime(N + 1, true),
          minfactor(N + 1, -1) {
        isprime[1] = false;
        minfactor[1] = 1;

        for (int p = 2; p <= N; ++p) {
            // すでに合成数であるものはスキップする
            if (!isprime[p])
                continue;

            // p についての情報更新
            minfactor[p] = p;

            // p 以外の p の倍数から素数ラベルを剥奪
            for (int q = p * 2; q <= N; q += p) {
                // q は合成数なのでふるい落とす
                isprime[q] = false;

                // q は p で割り切れる旨を更新
                if (minfactor[q] == -1)
                    minfactor[q] = p;
            }
        }
    }

    // 高速素因数分解
    // pair (素因子, 指数) の vector を返す
    vector<pair<ll, ll>> factorize(int n) {
        vector<pair<ll, ll>> res;
        while (n > 1) {
            int p = minfactor[n];
            int exp = 0;

            // n で割り切れる限り割る
            while (minfactor[n] == p) {
                n /= p;
                ++exp;
            }
            res.emplace_back(p, exp);
        }
        return res;
    }

    // 高速約数列挙
    vector<int> divisors(int n) {
        vector<int> res({1});

        // n を素因数分解 (メンバ関数使用)
        auto pf = factorize(n);

        // 約数列挙
        for (auto p : pf) {
            int s = (int)res.size();
            for (int i = 0; i < s; ++i) {
                int v = 1;
                for (int j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        return res;
    }
};

素因数分解

計算量 $O(\sqrt{N})$

https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/NTL_1_A/judge/10351217/C++23

// prime, cnt
vector<pair<ll, ll>> factor(ll n) {
    vector<pair<ll, ll>> ps;
    ll t = n;
    for (int i = 2; i * i <= n; i++) {
        if (t % i == 0) {
            ll cnt = 0;
            while (t % i == 0) {
                t /= i;
                cnt++;
            }
            ps.emplace_back(i, cnt);
        }
    }
    if (t > 1)
        ps.emplace_back(t, 1);

    return ps;
}

行列

$H \times W$ の行列 $A$ を考える. $A$ に以下の操作を加えたでできた行列を $A^\prime$ とする. このとき $A^\prime$ の $(i^\prime, j^\prime)$ 成分と $A$ の $(i,j)$ 成分の対応は以下の通りである.

各操作を愚直に行うと $O(HW)$ かかるが, index のみを更新することで $O(H+W)$ に計算量を落とすことができる.

rotr90

$ i^\prime = j \\\\ j^\prime = H - 1 - i $

rotl90

$ i^\prime = W - 1 - j \\\\ j^\prime = i $

transpose

$ i^\prime = j \\\\ j^\prime = i $

上下反転

$ i^\prime = H - 1 - i \\\\ j^\prime = j $

左右反転

$$ i^\prime = i \\\\ j^\prime = W - 1 - j $$

#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

template <typename T>
struct Matrix {
    Matrix(int h, int w)
        : isSwap(false), H(h), W(w), grid(h, vector<T>(w, 0)), xid(h), yid(w) {
        rep(i, h) xid[i] = i;
        rep(i, w) yid[i] = i;
    }

    T find(int x, int y) {
        P p = index(x, y);
        return grid[p.first][p.second];
    }

    void set(int x, int y, T val) {
        P p = index(x, y);
        grid[p.first][p.second] = val;
    }

    void rotr90() {
        isSwap = !isSwap;
        vector<int> new_yid(H);
        rep(i, H) new_yid[i] = H - 1 - xid[i];
        swap(H, W);
        xid = yid;
        yid = new_yid;
    }

    void rotl90() {
        isSwap = !isSwap;
        vector<int> new_xid(W);
        rep(i, W) new_xid[i] = W - 1 - yid[i];
        swap(H, W);
        yid = xid;
        xid = new_xid;
    }

    void topbottom() {
        rep(i, H / 2) swap(xid[i], xid[H - 1 - i]);
    }

    void leftright() {
        rep(i, W / 2) swap(yid[i], yid[W - 1 - i]);
    }

    void transpose() {
        isSwap = !isSwap;
        swap(xid, yid);
        swap(H, W);
    }

    void print() {
        rep(i, H) {
            rep(j, W) {
                cout << find(i, j) << " ";
            }
            cout << endl;
        }
    }

   private:
    bool isSwap;
    int H, W;
    vector<vector<T>> grid;

    // 新しい行列の index と original の行列の index との対応表
    // 新しい行列の i, j 成分は
    // swap is false のとき
    //   grid[xid[i]][yid[j]]
    // swap is true のとき
    //   grid[yid[j]][xid[i]]
    vector<int> xid, yid;

    pair<int, int> index(int x, int y) {
        int i = xid[x];
        int j = yid[y];
        if (isSwap)
            swap(i, j);
        return {i, j};
    }
};

void solve() {
    int h = 2, w = 3;
    Matrix<char> mat(2, 3);
    rep(i, h) rep(j, w) mat.set(i, j, 'a' + i * w + j);
    printf("original\n");
    mat.print();
    cout << endl;

    printf("rotr90\n");
    mat.rotr90();
    mat.print();
    cout << endl;

    printf("set 'z' at (0, 1)\n");
    mat.set(0, 1, 'z');
    mat.print();
    cout << endl;

    printf("rotr90\n");
    mat.rotr90();
    mat.print();
    cout << endl;

    printf("rotl90\n");
    mat.rotl90();
    mat.print();
    cout << endl;

    printf("transpose\n");
    mat.transpose();
    mat.print();
    cout << endl;
}

int main() {
    solve();
    return 0;
}

output

original
a b c
d e f

rotr90
d a
e b
f c

set 'z' at (0, 1)
d z
e b
f c

rotr90
f e d
c b z

rotl90
d z
e b
f c

transpose
d e f
z b c

べき乗

#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using vvll = vector<vector<ll>>;
ll MOD = ((ll)1e9);

struct Matrix {
    vvll data;

    Matrix(vvll data) { this->data = data; }

    Matrix operator*(const Matrix& other) {
        int n = data.size();
        int m = other.data[0].size();
        int l = other.data.size();
        vvll res(n, vll(m, 0));
        rep(i, n) rep(j, m) rep(k, l) {
            res[i][j] += data[i][k] * other.data[k][j];
            res[i][j] %= MOD;
        }
        return Matrix(res);
    }

    Matrix exp(ll k) {
        int n = data.size();
        Matrix res(vvll(n, vll(n, 0)));
        rep(i, n) res.data[i][i] = 1;
        Matrix a = *this;
        while (k > 0) {
            if (k & 1)
                res = res * a;
            a = a * a;
            k >>= 1;
        }
        return res;
    }
};

ランレングス圧縮 (Run Length Encoding)

template <typename T>
vector<pair<T, int>> runLengthEncode(const vector<T>& input) {
    vector<pair<T, int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

vector<pair<char, int>> runLengthEncode(const string& input) {
    vector<pair<char, int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

最長増加部分列 (LIS: Longest Increasing Subsequence)

数列 $A=a_0,a_1,\cdots, a_{n−1}$ の最長増加部分列 (LIS: Longest Increasing Subsequence) とは数列 $A$ の増加部分列 $a_{i_0}, \cdots, a_{i_k}$ ($0 \leq i_0 < i_1 < \cdots < i_k < n$ かつ $a_{i_0} < a_{i_1} < \cdots < a_{i_k}$) のうち最も $k$ が大きいもの.

// is_strong = true のとき increasing
// is_strong = false のとき non-decreasing
int LIS(vector<int>& A, bool is_strong) {
    int n = A.size();
    vector<int> dp(n, INF);

    rep(i, n) {
        // A_{i_{k}} < A_{i_{k+1}}
        if (is_strong)
            *lower_bound(all(dp), A[i]) = A[i];
        // A_{i_{k}} <= A_{i_{k+1}}
        else
            *upper_bound(all(dp), A[i]) = A[i];
    }

    return lower_bound(all(dp), INF) - dp.begin();
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    cout << LIS(a, true) << endl;
}

最短経路

ダイクストラ法 (Dijkstra)

https://judge.yosupo.jp/submission/263372

const ll INF = (ll)2e18 + 9;

struct Edge {
    int to;
    long long int weight;
};

bool operator>(const Edge& a, const Edge& b) {
    return a.weight > b.weight;
}

using Graph = vector<vector<Edge>>;

struct Dijkstra {
    int n;  // ノード数
    Graph graph;
    vector<long long int> dist;  // start からの最短距離
    vector<int> from;            // from[i]: i 番目のノードにどこから来たか
    int start = -1;

    Dijkstra(int n)
        : n(n), graph(n), dist(n, INF), from(n, -1) {}

    void add_edge(int from, int to, long long int weight) {
        graph[from].push_back({to, weight});
    }

    void run(int start) {
        dist[start] = 0;
        this->start = start;

        // cost, node
        using P = pair<long long int, int>;
        priority_queue<P, vector<P>, greater<P>> pq;
        pq.push({0, start});

        while (pq.size()) {
            auto [cost, node] = pq.top();
            pq.pop();

            if (dist[node] < cost)
                continue;

            for (auto [to, weight] : graph[node]) {
                if (dist[to] > dist[node] + weight) {
                    dist[to] = dist[node] + weight;
                    from[to] = node;
                    pq.push({dist[to], to});
                }
            }
        }
    }

    // start から fin までの最短距離.  到達不可のときは -1 を返す
    long long int distance(int fin) {
        if (dist[fin] == INF)
            return -1;
        return dist[fin];
    }

    // start -> fin への経路
    vector<int> path(int fin) {
        vector<int> ans = {fin};
        int now = fin;
        while (now != start) {
            now = from[now];
            ans.push_back(now);
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};

void solve() {
    int N, M, s, t;
    cin >> N >> M >> s >> t;

    Dijkstra graph(N);
    rep(i, M) {
        ll a, b, c;
        cin >> a >> b >> c;
        graph.add_edge(a, b, c);
    }

    graph.run(s);
    if (graph.distance(t) == -1) {
        cout << -1 << endl;
        return;
    }

    vint path = graph.path(t);
    cout << graph.distance(t) << ' ' << path.size() - 1 << endl;
    rep(i, path.size() - 1) {
        cout << path[i] << ' ' << path[i + 1] << endl;
    }
}

最小全域木(minimum spanning tree)

プリム法

適当な頂点(本当にどこからでもいい)を起点にして, まだ訪れていない頂点への最小のコストの辺を採用していく. すでに訪れた頂点への辺は捨てる.

struct Edge {
    int to;
    ll cost;
};

bool operator>(const Edge& a, const Edge& b) {
    return a.cost > b.cost;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n);
    rep(i, m) {
        int s, t;
        ll w;
        cin >> s >> t >> w;
        graph[s].push_back({t, w});
        graph[t].push_back({s, w});
    }

    vint visited(n, 0);
    visited[0] = 1;
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    for (auto edge : graph[0])
        pq.push(edge);
    vector<Edge> mst;
    while (pq.size()) {
        auto t = pq.top();
        pq.pop();
        if (visited[t.to])
            continue;
        visited[t.to] = 1;
        mst.push_back(t);
        for (auto edge : graph[t.to]) {
            if (visited[edge.to])
                continue;
            pq.push(edge);
        }
    }

    ll tot = 0;
    for (auto edge : mst) {
        tot += edge.cost;
    }
    cout << tot << endl;
}

クラスカル法

全ての辺をコストが小さい順に見ていき, 見ている辺をつないだときにサイクルができなければその辺を採用, それ以外のときは捨てる. サイクルの検出には Union Find を使うのが定石.

struct Edge {
    int from;
    int to;
    ll cost;
};

bool operator<(const Edge& a, const Edge& b) {
    return a.cost < b.cost;
}

struct UnionFind {
    vint d;
    UnionFind(int n)
        : d(n, -1) {}
    int leader(int x) {
        if (d[x] < 0)
            return x;
        return d[x] = leader(d[x]);
    }
    void merge(int x, int y) {
        x = leader(x), y = leader(y);
        if (x == y)
            return;
        if (d[x] < d[y])
            swap(x, y);
        d[x] += d[y];
        d[y] = x;
    }
    bool same(int x, int y) {
        return leader(x) == leader(y);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    rep(i, m) {
        int s, t;
        ll w;
        cin >> s >> t >> w;
        edges.push_back({s, t, w});
        edges.push_back({t, s, w});
    }
    sort(all(edges));

    vector<Edge> mst_edges;
    UnionFind uf(n);
    for (auto [from, to, cost] : edges) {
        if (!uf.same(from, to)) {
            mst_edges.push_back({from, to, cost});
            uf.merge(from, to);
        }
    }

    ll tot = 0;
    for (auto edge : mst_edges)
        tot += edge.cost;
    cout << tot << endl;
}

Segment tree (セグメント木)

ACL の使い方は別途まとめた

ソラで書くセグメント木から ACL へ移行する

RMQ (Range Minimum Query)

一点更新、区間最小値

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A
- 再帰版
  - https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/DSL_2_A/judge/10276204/C++23
- 非再帰版
  - https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/DSL_2_A/judge/10276844/C++23

struct RMQ {
    vector<ll> seg;
    ll e = (1ll << 31) - 1;
    int len = 1;

    RMQ(int n) {
        while (n > len)
            len *= 2;
        seg.resize(len * 2, e);
    }

    void set(int p, ll x) {
        p += len;
        seg[p] = x;
        while (p / 2) {
            p /= 2;
            seg[p] = min(seg[2 * p], seg[2 * p + 1]);
        }
    }

    ll prod(int l, int r) {
        l += len, r += len;
        ll ans = (1ll << 31) - 1;
        while (l < r) {
            if (l % 2 == 1) {
                ans = min(ans, seg[l]);
                l++;
            }
            l /= 2;
            if (r % 2 == 1) {
                ans = min(ans, seg[r - 1]);
                r--;
            }
            r /= 2;
        }

        return ans;
    }

    ll prod_rec(int l, int r) {
        return _prod_rec(l, r, 0, len, 1);
    }

    ll _prod_rec(int ql, int qr, int sl, int sr, int p) {
        if (qr <= sl || sr <= ql)
            return e;
        if (ql <= sl && sr <= qr)
            return seg[p];
        int sm = (sl + sr) / 2;
        ll lmin = _prod_rec(ql, qr, sl, sm, p * 2);
        ll rmin = _prod_rec(ql, qr, sm, sr, p * 2 + 1);
        return min(lmin, rmin);
    }
};

RSQ (Range Sum Query)

一点加算、区間和

https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B
- 非再帰版
  - https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/DSL_2_B/judge/10276127/C++23
- 再帰版
  - https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/DSL_2_B/judge/10276849/C++23

struct RSQ {
    vll seg;
    ll e = 0;
    ll len = 1;

    RSQ(int n) {
        while (n > len)
            len *= 2;
        seg.resize(len * 2, e);
    }

    void add(int p, ll x) {
        p += len;
        seg[p] += x;
        while (p / 2) {
            p /= 2;
            seg[p] += x;
        }
    }

    ll sum(int l, int r) {
        l += len, r += len;
        ll ans = e;

        while (l < r) {
            if (l & 1) {
                ans += seg[l];
                l++;
            }
            l /= 2;
            if (r & 1) {
                ans += seg[r - 1];
                r--;
            }
            r /= 2;
        }

        return ans;
    }

    ll sum_rec(int l, int r) {
        return _sum_rec(l, r, 0, len, 1);
    }

    ll _sum_rec(int ql, int qr, int sl, int sr, int p) {
        if (qr <= sl || sr <= ql)
            return e;
        if (ql <= sl && sr <= qr)
            return seg[p];
        int sm = (sl + sr) / 2;
        ll lsum = _sum_rec(ql, qr, sl, sm, p * 2);
        ll rsum = _sum_rec(ql, qr, sm, sr, p * 2 + 1);
        return lsum + rsum;
    }
};

RAQ (Range Add Query)

区間加算、一点取得

struct RAQ {
    vll seg;
    ll e = 0;
    int len = 1;

    RAQ(int n) {
        while (n > len)
            len *= 2;
        seg.resize(len * 2, e);
    }

    ll get(int p) {
        p += len;
        ll ans = seg[p];
        while (p / 2) {
            p /= 2;
            ans += seg[p];
        }
        return ans;
    }

    void add(int l, int r, ll x) {
        l += len, r += len;
        while (l < r) {
            if (l & 1) {
                seg[l] += x;
                l++;
            }
            l /= 2;
            if (r & 1) {
                seg[r - 1] += x;
                r--;
            }
            r /= 2;
        }
    }

    void add_rec(int l, int r, ll x) {
        _add_rec(l, r, 0, len, x, 1);
    }

    void _add_rec(int ql, int qr, int sl, int sr, ll x, int p) {
        if (sr <= ql || qr <= sl)
            return;
        if (ql <= sl && sr <= qr) {
            seg[p] += x;
            return;
        }
        int sm = (sl + sr) / 2;
        _add_rec(ql, qr, sl, sm, x, p * 2);
        _add_rec(ql, qr, sm, sr, x, p * 2 + 1);
    }
};

RUQ (Range Update Query)

区間更新、一点取得

いつ更新したものかという情報も付け加えて値の更新を管理する

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D
- https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/DSL_2_D/judge/10276168/C++23
- 再帰版
  - https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/DSL_2_D/judge/10276853/C++23

struct RUQ {
    vector<ll> seg;
    vint updated_at;
    ll e = (1ll << 31) - 1;
    int len = 1;
    int cnt = 0;

    RUQ(int n) {
        while (n > len)
            len *= 2;
        seg.resize(len * 2, e);
        updated_at.resize(len * 2, -1);
    }

    void update(int l, int r, ll x) {
        cnt++;
        l += len, r += len;
        while (l < r) {
            if (l & 1) {
                seg[l] = x;
                updated_at[l] = cnt;
                l++;
            }
            l /= 2;
            if (r & 1) {
                seg[r - 1] = x;
                updated_at[r - 1] = cnt;
                r--;
            }
            r /= 2;
        }
    }

    void update_rec(int l, int r, ll x) {
        cnt++;
        _update_rec(l, r, 0, len, x, 1);
    }

    void _update_rec(int ql, int qr, int sl, int sr, ll x, int p) {
        if (sr <= ql || qr <= sl)
            return;
        if (ql <= sl && sr <= qr) {
            seg[p] = x;
            updated_at[p] = cnt;
            return;
        }
        int sm = (sl + sr) / 2;
        _update_rec(ql, qr, sl, sm, x, p * 2);
        _update_rec(ql, qr, sm, sr, x, p * 2 + 1);
    }

    ll find(int p) {
        p += len;
        ll ans = seg[p];
        int t = updated_at[p];
        while (p / 2) {
            p /= 2;
            ll nv = seg[p];
            ll nt = updated_at[p];
            if (nt > t) {
                ans = nv;
                t = nt;
            }
        }
        return ans;
    }
};

RSQ and RAQ

区間和、区間加算

https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/DSL_2_G/judge/10276973/C++23

struct RSQRAQ {
    vll seg;
    vll lazy;
    int len = 1;
    ll e = 0;
    ll id = 0;

    RSQRAQ(int n) {
        while (n > len)
            len *= 2;
        seg.resize(len * 2, e);
        lazy.resize(len * 2, id);
    }

    void eval(int sl, int sr, int p) {
        if (lazy[p] == id)
            return;
        seg[p] += lazy[p];
        if (sr - sl > 1) {
            ll x = lazy[p];
            lazy[p * 2] += x / 2;
            lazy[p * 2 + 1] += x / 2;
        }
        lazy[p] = 0;
    }

    ll sum(int l, int r) {
        auto rec = [&](auto rec, int ql, int qr, int sl, int sr, int p) -> ll {
            eval(sl, sr, p);
            if (sr <= ql || qr <= sl) {
                return id;
            }
            if (ql <= sl && sr <= qr) {
                return seg[p];
            }
            int sm = (sl + sr) / 2;
            ll lsum = rec(rec, ql, qr, sl, sm, p * 2);
            ll rsum = rec(rec, ql, qr, sm, sr, p * 2 + 1);

            return lsum + rsum;
        };

        return rec(rec, l, r, 0, len, 1);
    }

    void add(int s, int t, ll x) {
        auto rec = [&](auto rec, int ql, int qr, int sl, int sr, ll x, int p) {
            eval(sl, sr, p);

            if (qr <= sl || sr <= ql)
                return;
            if (ql <= sl && sr <= qr) {
                lazy[p] += (sr - sl) * x;
                eval(sl, sr, p);
                return;
            }

            int sm = (sl + sr) / 2;
            rec(rec, ql, qr, sl, sm, x, p * 2);
            rec(rec, ql, qr, sm, sr, x, p * 2 + 1);
            seg[p] = seg[p * 2] + seg[p * 2 + 1];
        };

        rec(rec, s, t, 0, len, x, 1);
    }
};

RMQ and RAQ

区間最小値、区間加算

struct RMQRAQ {
    vll seg;
    vll lazy;
    int len = 1;
    ll e = 0;
    ll id = INF;

    RMQRAQ(int n) {
        while (n > len)
            len *= 2;
        seg.resize(len * 2, e);
        lazy.resize(len * 2, id);
    }

    void eval(int sl, int sr, int p) {
        if (lazy[p] == id)
            return;
        seg[p] += lazy[p];
        if (sr - sl > 1) {
            ll x = lazy[p];
            if (lazy[p * 2] == id)
                lazy[p * 2] = x;
            else
                lazy[p * 2] += x;

            if (lazy[p * 2 + 1] == id)
                lazy[p * 2 + 1] = x;
            else
                lazy[p * 2 + 1] += x;
        }
        lazy[p] = id;
    }

    ll find(int l, int r) {
        auto rec = [&](auto rec, int ql, int qr, int sl, int sr, int p) -> ll {
            eval(sl, sr, p);
            if (sr <= ql || qr <= sl) {
                return id;
            }
            if (ql <= sl && sr <= qr) {
                return seg[p];
            }
            int sm = (sl + sr) / 2;
            ll lmin = rec(rec, ql, qr, sl, sm, p * 2);
            ll rmin = rec(rec, ql, qr, sm, sr, p * 2 + 1);

            return min(lmin, rmin);
        };

        return rec(rec, l, r, 0, len, 1);
    }

    void add(int s, int t, ll x) {
        auto rec = [&](auto rec, int ql, int qr, int sl, int sr, ll x, int p) {
            eval(sl, sr, p);

            if (qr <= sl || sr <= ql)
                return;
            if (ql <= sl && sr <= qr) {
                if (lazy[p] == id)
                    lazy[p] = 0;
                lazy[p] += x;
                eval(sl, sr, p);
                return;
            }

            int sm = (sl + sr) / 2;
            rec(rec, ql, qr, sl, sm, x, p * 2);
            rec(rec, ql, qr, sm, sr, x, p * 2 + 1);
            seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
        };

        rec(rec, s, t, 0, len, x, 1);
    }
};

転倒数

https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/ALDS1_5_D/judge/10376676/C++23

struct Segtree {
    int sz;
    vll data;

    Segtree(int n) {
        int i = 0;
        while ((1 << i) < n)
            i++;
        sz = 1 << i;
        data.resize(sz * 2);
    }

    void set(int p, ll x) {
        p += sz;
        data[p] = x;
        while (p / 2) {
            p /= 2;
            data[p] = data[p * 2] + data[p * 2 + 1];
        }
    }

    ll prod(int l, int r) {
        l += sz, r += sz;
        ll ans = 0;
        while (l < r) {
            if (l % 2 == 1) {
                ans += data[l];
                l++;
            }
            l /= 2;
            if (r % 2 == 1) {
                ans += data[r - 1];
                r--;
            }
            r /= 2;
        }
        return ans;
    }
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vint A(N);
    rep(i, N) {
        cin >> A[i];
    }

    vector<pair<int, int>> ids;
    rep(i, N) {
        ids.emplace_back(A[i], i);
    }
    sort(all(ids));

    Segtree seg(N);
    ll ans = 0;
    for (auto [_, i] : ids) {
        ans += seg.prod(i, N + 1);
        seg.set(i, 1);
    }
    cout << ans << endl;
}

Rolling Hash

https://onlinejudge.u-aizu.ac.jp/status/users/goropikari/submissions/1/ALDS1_14_B/judge/10319713/C++23

ll modpow(ll x, ll n, ll mod) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

struct RollingHash {
    vll data;
    const ll p = 1000000009;
    const ll mod = 1000000021;

    RollingHash(vll& v) {
        int n = v.size();
        data.resize(n + 1);
        rep(i, n) {
            data[i + 1] = (data[i] * p % mod) + v[i];
            data[i + 1] %= mod;
        }
    };

    // [l,r) の範囲の hash 値
    ll sub(ll l, ll r) {
        ll m = r - l;
        ll x = data[r] - data[l] * modpow(p, m, mod) % mod;
        x += mod;
        x %= mod;
        return x;
    }
};