test/aoj_0425.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0425"

#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>

#include "algorithm/mo.cpp"

class range_function {
  size_t M_n;
  size_t M_l = 0;
  size_t M_r = 0;
  std::vector<std::pair<size_t, size_t>> M_op;
  std::vector<size_t> M_p, M_q;

  void M_swap(size_t a, size_t b) {
    std::swap(M_q[M_p[a]], M_q[M_p[b]]);
    std::swap(M_p[a], M_p[b]);
  }

public:
  range_function() = default;
  range_function(size_t n, std::vector<std::pair<size_t, size_t>> const& ab):
    M_n(n), M_op(ab), M_p(n), M_q(n)
  {
    std::iota(M_p.begin(), M_p.end(), 0);
    std::iota(M_q.begin(), M_q.end(), 0);
  }

  void push_back() { auto [a, b] = M_op[M_r++]; M_swap(a, b); }
  void push_front() { auto [a, b] = M_op[--M_l]; M_swap(M_q[a], M_q[b]); }
  void pop_back() { auto [a, b] = M_op[--M_r]; M_swap(a, b); }
  void pop_front() { auto [a, b] = M_op[M_l++]; M_swap(M_q[a], M_q[b]); }
  size_t size() const { return M_n; }

  size_t operator ()(std::pair<size_t, int> const& q) {
    auto [x, type] = q;
    return ((type == 1)? M_p[x]: M_q[x]);
  }
};

int main() {
  size_t n, k, q;
  scanf("%zu %zu %zu", &n, &k, &q);

  std::vector<std::pair<size_t, size_t>> ab(k);
  for (auto& [a, b]: ab) scanf("%zu %zu", &a, &b), --a, --b;

  using query_type = std::tuple<size_t, size_t, std::pair<size_t, int>>;
  std::vector<query_type> qs(q);
  for (auto& [s, t, p]: qs) {
    scanf("%d %zu %zu %zu", &p.second, &s, &t, &p.first);
    --s;
    --p.first;
  }

  for (auto res: mo(range_function(n, ab), qs))
    printf("%zu\n", res+1);
}

#line 1 "test/aoj_0425.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0425"

#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>

#line 1 "algorithm/mo.cpp"



/**
 * @brief Mo's algorithm
 * @author えびちゃん
 */

#line 14 "algorithm/mo.cpp"

#line 1 "integer/sqrt.cpp"



/**
 * @brief 整数の平方根
 * @author えびちゃん
 */

#include <climits>

template <typename Tp>
Tp isqrt(Tp n) {
  if (n <= 1) return n;
  Tp lb = 1;
  Tp ub = static_cast<Tp>(1) << (CHAR_BIT * (sizeof(Tp) / 2));
  while (ub-lb > 1) {
    Tp mid = (lb+ub) >> 1;
    ((mid*mid <= n)? lb: ub) = mid;
  }
  return lb;
}


#line 16 "algorithm/mo.cpp"

template <typename Rf, typename Args>
auto mo(Rf&& rf, std::vector<std::tuple<size_t, size_t, Args>> const& qs)
  -> std::vector<decltype(rf(std::declval<Args>()))>
{
  if (qs.empty()) return {};
  using value_type = decltype(rf(std::declval<Args>()));
  size_t n = rf.size();
  size_t q = qs.size();
  std::vector<value_type> res(q);
  size_t b = n / isqrt(q);
  std::vector<size_t> is(q);
  std::iota(is.begin(), is.end(), 0);
  std::sort(is.begin(), is.end(), [&](size_t i0, size_t i1) {
    size_t l0 = std::get<0>(qs[i0]) / b;
    size_t r0 = std::get<1>(qs[i0]);
    size_t l1 = std::get<0>(qs[i1]) / b;
    size_t r1 = std::get<1>(qs[i1]);
    if (l0 != l1) return l0 < l1;
    if (r0 != r1) return r0 < r1;
    return false;
  });

  size_t l = 0;
  size_t r = 0;
  for (auto i: is) {
    auto const& [l0, r0, x] = qs[i];
    while (r < r0) rf.push_back(), ++r;
    while (l > l0) rf.push_front(), --l;
    while (l < l0) rf.pop_front(), ++l;
    while (r > r0) rf.pop_back(), --r;
    res[i] = rf(x);
    l = l0;
    r = r0;
  }
  return res;
}


#line 12 "test/aoj_0425.test.cpp"

class range_function {
  size_t M_n;
  size_t M_l = 0;
  size_t M_r = 0;
  std::vector<std::pair<size_t, size_t>> M_op;
  std::vector<size_t> M_p, M_q;

  void M_swap(size_t a, size_t b) {
    std::swap(M_q[M_p[a]], M_q[M_p[b]]);
    std::swap(M_p[a], M_p[b]);
  }

public:
  range_function() = default;
  range_function(size_t n, std::vector<std::pair<size_t, size_t>> const& ab):
    M_n(n), M_op(ab), M_p(n), M_q(n)
  {
    std::iota(M_p.begin(), M_p.end(), 0);
    std::iota(M_q.begin(), M_q.end(), 0);
  }

  void push_back() { auto [a, b] = M_op[M_r++]; M_swap(a, b); }
  void push_front() { auto [a, b] = M_op[--M_l]; M_swap(M_q[a], M_q[b]); }
  void pop_back() { auto [a, b] = M_op[--M_r]; M_swap(a, b); }
  void pop_front() { auto [a, b] = M_op[M_l++]; M_swap(M_q[a], M_q[b]); }
  size_t size() const { return M_n; }

  size_t operator ()(std::pair<size_t, int> const& q) {
    auto [x, type] = q;
    return ((type == 1)? M_p[x]: M_q[x]);
  }
};

int main() {
  size_t n, k, q;
  scanf("%zu %zu %zu", &n, &k, &q);

  std::vector<std::pair<size_t, size_t>> ab(k);
  for (auto& [a, b]: ab) scanf("%zu %zu", &a, &b), --a, --b;

  using query_type = std::tuple<size_t, size_t, std::pair<size_t, int>>;
  std::vector<query_type> qs(q);
  for (auto& [s, t, p]: qs) {
    scanf("%d %zu %zu %zu", &p.second, &s, &t, &p.first);
    --s;
    --p.first;
  }

  for (auto res: mo(range_function(n, ab), qs))
    printf("%zu\n", res+1);
}