verify/aoj-0425-mo_algorithm.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0425

Depends on

• Mo's Algorithm（クエリ平方分割） (algorithm/Others/mo_algorithm.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0425"

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

#include "../algorithm/Others/mo_algorithm.hpp"

int main() {
    int n;
    int k;
    int q;
    std::cin >> n >> k >> q;

    std::vector<std::pair<int, int> > vp(k);
    for(auto &[a, b] : vp) {
        std::cin >> a >> b;
        a--, b--;
    }

    std::vector<std::pair<int, int> > queries(q);
    algorithm::Mo mo(k, q);
    for(int i = 0; i < q; ++i) {
        int type;
        int s, t;
        int x;
        std::cin >> type >> s >> t >> x;
        s--, x--;

        queries[i] = std::pair<int, int>(type, x);
        mo.insert(s, t);
    }

    std::vector<int> ans(q);
    std::vector<int> alpha(n), inv(n);
    std::iota(alpha.begin(), alpha.end(), 0);
    std::iota(inv.begin(), inv.end(), 0);
    auto swap_l = [&](int itr) -> void {
        const auto &[a, b] = vp[itr];
        std::swap(alpha[inv[a]], alpha[inv[b]]);
        std::swap(inv[a], inv[b]);
    };
    auto swap_r = [&](int itr) -> void {
        const auto &[a, b] = vp[itr];
        std::swap(inv[alpha[a]], inv[alpha[b]]);
        std::swap(alpha[a], alpha[b]);
    };
    auto solve = [&](int idx) -> void {
        const auto &[type, x] = queries[idx];
        ans[idx] = (type == 1 ? alpha[x] + 1 : inv[x] + 1);
    };
    mo.execute(swap_l, swap_l, swap_r, swap_r, solve);

    for(auto elem : ans) std::cout << elem << "\n";
}

#line 1 "verify/aoj-0425-mo_algorithm.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0425"

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

#line 1 "algorithm/Others/mo_algorithm.hpp"



/**
 * @brief Mo's Algorithm（クエリ平方分割）
 * @docs docs/Others/mo_algorithm.md
 */

#include <algorithm>
#include <cassert>
#include <cmath>
#include <tuple>
#line 14 "algorithm/Others/mo_algorithm.hpp"

namespace algorithm {

// Mo's Algorithm（クエリ平方分割）.
class Mo {
    int m_len;                                          // m_len:=(区間の長さ).
    int m_q;                                            // m_q:=(クエリ数).
    std::vector<std::tuple<int, int, int> > m_queries;  // m_queries[i]:=(i番目の区間クエリ). tuple of (left, right, index).

    void sort_queries() {
        if(m_q == 0) return;
        const int width = std::max(m_len / (int)std::sqrt(m_q), 1);  // width:=N/√Q.
        std::sort(m_queries.begin(), m_queries.end(), [&width](const std::tuple<int, int, int> &a, const std::tuple<int, int, int> &b) -> bool {
            const auto &[al, ar, _] = a;
            const auto &[bl, br, __] = b;
            int a_block = al / width, b_block = bl / width;
            if(a_block == b_block) return (a_block & 1 ? ar > br : ar < br);
            return a_block < b_block;
        });
    }

public:
    Mo() : Mo(0) {}
    explicit Mo(size_t n) : m_len(n), m_q(0) {}
    explicit Mo(size_t n, size_t q) : Mo(n) {
        m_queries.reserve(q);
    }

    // 区間[l,r)についてのクエリを追加する．
    void insert(int l, int r) {
        assert(0 <= l and l < r and r <= m_len);
        m_queries.emplace_back(l, r, m_q++);
    }
    // 各クエリを実行する．O(Q*logQ+α*N*√Q).
    template <class F1, class F2, class F3>
    void execute(const F1 &add, const F2 &del, const F3 &solve) { execute(add, del, add, del, solve); }
    template <class F1, class F2, class F3, class F4, class F5>
    void execute(const F1 &add_l, const F2 &del_l, const F3 &add_r, const F4 &del_r, const F5 &solve) {
        sort_queries();
        int l = 0, r = 0;
        for(const auto &[nl, nr, idx] : m_queries) {
            while(nl < l) add_l(--l);
            while(r < nr) add_r(r++);
            while(l < nl) del_l(l++);
            while(nr < r) del_r(--r);
            solve(idx);
        }
    }
    void reset() {
        m_queries.clear();
        m_q = 0;
    }
};

}  // namespace algorithm


#line 9 "verify/aoj-0425-mo_algorithm.test.cpp"

int main() {
    int n;
    int k;
    int q;
    std::cin >> n >> k >> q;

    std::vector<std::pair<int, int> > vp(k);
    for(auto &[a, b] : vp) {
        std::cin >> a >> b;
        a--, b--;
    }

    std::vector<std::pair<int, int> > queries(q);
    algorithm::Mo mo(k, q);
    for(int i = 0; i < q; ++i) {
        int type;
        int s, t;
        int x;
        std::cin >> type >> s >> t >> x;
        s--, x--;

        queries[i] = std::pair<int, int>(type, x);
        mo.insert(s, t);
    }

    std::vector<int> ans(q);
    std::vector<int> alpha(n), inv(n);
    std::iota(alpha.begin(), alpha.end(), 0);
    std::iota(inv.begin(), inv.end(), 0);
    auto swap_l = [&](int itr) -> void {
        const auto &[a, b] = vp[itr];
        std::swap(alpha[inv[a]], alpha[inv[b]]);
        std::swap(inv[a], inv[b]);
    };
    auto swap_r = [&](int itr) -> void {
        const auto &[a, b] = vp[itr];
        std::swap(inv[alpha[a]], inv[alpha[b]]);
        std::swap(alpha[a], alpha[b]);
    };
    auto solve = [&](int idx) -> void {
        const auto &[type, x] = queries[idx];
        ans[idx] = (type == 1 ? alpha[x] + 1 : inv[x] + 1);
    };
    mo.execute(swap_l, swap_l, swap_r, swap_r, solve);

    for(auto elem : ans) std::cout << elem << "\n";
}

Back to top page