#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0425"
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
#include "Mylib/Algorithm/mo_algorithm.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"
#include "Mylib/IO/input_tuples.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, K, Q;
std::cin >> N >> K >> Q;
auto [a, b] = hl::input_tuple_vector<int, int>(K);
for (auto &x : a) --x;
for (auto &x : b) --x;
std::vector<std::tuple<int, int, int, int>> qs;
for (auto [type, s, t, x] : hl::input_tuples<int, int, int, int>(Q)) {
--s, --t, --x;
qs.emplace_back(type, s, t, x);
}
std::vector<int> p(N), q(N);
std::iota(p.begin(), p.end(), 0);
std::iota(q.begin(), q.end(), 0);
std::vector<int> ans(Q);
auto left =
[&](int i) {
std::swap(q[p[q[a[i]]]], q[p[q[b[i]]]]);
std::swap(p[q[a[i]]], p[q[b[i]]]);
};
auto right =
[&](int i) {
std::swap(q[p[a[i]]], q[p[b[i]]]);
std::swap(p[a[i]], p[b[i]]);
};
auto query =
[&](int i) {
if (std::get<0>(qs[i]) == 1)
ans[i] = p[std::get<3>(qs[i])] + 1;
else
ans[i] = q[std::get<3>(qs[i])] + 1;
};
auto mo = hl::mo_algorithm(N, Q, left, right, left, right, query);
for (int i = 0; i < Q; ++i) mo.add(std::get<1>(qs[i]), std::get<2>(qs[i]) + 1);
mo.run();
for (int i = 0; i < Q; ++i) std::cout << ans[i] << "\n";
return 0;
}
#line 1 "test/aoj/0425/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0425"
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
#line 2 "Mylib/Algorithm/mo_algorithm.cpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#line 6 "Mylib/Algorithm/mo_algorithm.cpp"
namespace haar_lib {
template <typename AppendLeft, typename AppendRight, typename RemoveLeft, typename RemoveRight, typename Query>
class mo_algorithm {
int N_, Q_, index_, width_;
std::vector<int> left_, right_, ord_;
AppendLeft append_left_;
AppendRight append_right_;
RemoveLeft remove_left_;
RemoveRight remove_right_;
Query query_;
bool is_built_ = false;
public:
mo_algorithm() {}
mo_algorithm(
int N, int Q,
const AppendLeft &append_left, const AppendRight &append_right,
const RemoveLeft &remove_left, const RemoveRight &remove_right,
const Query &query) : N_(N), Q_(Q), index_(0), width_(std::sqrt(N)), left_(Q), right_(Q), ord_(Q), append_left_(append_left), append_right_(append_right), remove_left_(remove_left), remove_right_(remove_right), query_(query) {}
// [l, r)
void add(int l, int r) {
left_[index_] = l;
right_[index_] = r;
ord_[index_] = index_;
++index_;
}
void run() {
std::sort(
ord_.begin(), ord_.end(),
[&](int i, int j) {
const int a = left_[i] / width_, b = left_[j] / width_;
if (a == b) {
if (a & 1)
return right_[i] < right_[j];
else
return right_[i] > right_[j];
} else {
return a < b;
}
});
int q = 0;
int l = left_[ord_[0]], r = left_[ord_[0]];
for (int i = 0; i < Q_; ++i) {
int id = ord_[q++];
while (l != left_[id] or r != right_[id]) {
if (l > left_[id]) append_left_(--l);
if (l < left_[id]) remove_left_(l++);
if (r < right_[id]) append_right_(r++);
if (r > right_[id]) remove_right_(--r);
}
query_(id);
}
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 7 "Mylib/IO/input_tuple_vector.cpp"
namespace haar_lib {
template <typename T, size_t... I>
void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
}
template <typename T, size_t... I>
void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
}
template <typename... Args>
auto input_tuple_vector(int N) {
std::tuple<std::vector<Args>...> ret;
input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
for (int i = 0; i < N; ++i) {
input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
}
return ret;
}
} // namespace haar_lib
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 11 "test/aoj/0425/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, K, Q;
std::cin >> N >> K >> Q;
auto [a, b] = hl::input_tuple_vector<int, int>(K);
for (auto &x : a) --x;
for (auto &x : b) --x;
std::vector<std::tuple<int, int, int, int>> qs;
for (auto [type, s, t, x] : hl::input_tuples<int, int, int, int>(Q)) {
--s, --t, --x;
qs.emplace_back(type, s, t, x);
}
std::vector<int> p(N), q(N);
std::iota(p.begin(), p.end(), 0);
std::iota(q.begin(), q.end(), 0);
std::vector<int> ans(Q);
auto left =
[&](int i) {
std::swap(q[p[q[a[i]]]], q[p[q[b[i]]]]);
std::swap(p[q[a[i]]], p[q[b[i]]]);
};
auto right =
[&](int i) {
std::swap(q[p[a[i]]], q[p[b[i]]]);
std::swap(p[a[i]], p[b[i]]);
};
auto query =
[&](int i) {
if (std::get<0>(qs[i]) == 1)
ans[i] = p[std::get<3>(qs[i])] + 1;
else
ans[i] = q[std::get<3>(qs[i])] + 1;
};
auto mo = hl::mo_algorithm(N, Q, left, right, left, right, query);
for (int i = 0; i < Q; ++i) mo.add(std::get<1>(qs[i]), std::get<2>(qs[i]) + 1);
mo.run();
for (int i = 0; i < Q; ++i) std::cout << ans[i] << "\n";
return 0;
}
test/aoj/0425/main.test.cpp
Mo's algorithm
(Mylib/Algorithm/mo_algorithm.cpp)