#1175972 (C++23) No.3617 Swap

• 問題: No.3617 Swap
• ユーザー: kwm_t
• 提出日時: 2026-08-10 02:48:36
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 383 ms / 2,000 ms
• コード長: 5,385 bytes
• コンパイル時間: 2,168 ms
• コンパイル使用メモリ: 349,808 KB
• 実行使用メモリ: 42,240 KB
• 最終ジャッジ日時: 2026-08-10 02:48:53
• 合計ジャッジ時間: 14,449 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

サブタスク	配点	結果
サンプル	0 %	AC * 4
小課題1	5 %	AC * 3
小課題2	5 %	AC * 5
小課題3	15 %	AC * 14
小課題4	20 %	AC * 21
小課題5	25 %	AC * 8
小課題6	10 %	AC * 8
小課題7	20 %	AC * 56
合計	3 * 100% = 300 点

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_ALGORITHM_SEARCH_DOUBLING_HPP
#define KWM_T_ALGORITHM_SEARCH_DOUBLING_HPP

#include <vector>
#include <functional>
#include <utility>

namespace kwm_t::algorithm::search {
/**
 * @brief Doubling (Binary Lifting)
 *
 * 関数 f の k 回適用 f^k(x) を高速に求めるデータ構造。
 * nxt[v] = f(v) としたとき、
 * 2^i 回遷移した先を前計算することで O(log k) で遷移可能。
 *
 * value を持たせることで、遷移に伴う値（距離・重み・xor など）の
 * 累積も同時に計算できる。
 *
 * 典型用途:
 *   ・Functional Graph の k step
 *   ・テレポート問題
 *   ・祖先ジャンプ
 *   ・遷移コストの累積
 *
 * 計算量:
 *   構築 O(N log K)
 *   jump / jump_value / first_true : O(log K)
 *
 * @tparam T      遷移に付随する値の型
 * @tparam Merge  値をマージする関数 (例: std::plus)
 *
 * @param nxt     nxt[v] = v から1回遷移した先
 * @param value   各遷移に対応する値
 * @param log     最大ステップ数のビット長
 *
 * 制約 / 注意:
 *   ・first_true は単調性が必要
 *       f(jump(v,k)) が
 *       false false ... false true true ...
 *       の形になる必要がある
 *
 * 使用例:
 *   vector<int> nxt = {...};
 *   Doubling<> db(nxt);
 *   int v = db.jump(0, 1e18);
 *
 *   vector<long long> cost = {...};
 *   auto merge = [](auto a, auto b) { return a + b; };
 *   Doubling<long long, decltype(merge)> db2(nxt, cost, merge);
 *   auto [to, sum] = db2.jump_value(0, k);
 *
 * verified:
 *   https://atcoder.jp/contests/awc0025/submissions/74048140
 *   https://atcoder.jp/contests/abc438/submissions/74048565
 *   first_true
 *   https://atcoder.jp/contests/arc218/submissions/75493507
 */
struct DoublingNoValue {};
template<class T = DoublingNoValue, class Merge = std::plus<T>>
class Doubling {
public:
	int N;
	int LOG;

	Doubling(const std::vector<int>& nxt, int log = 60) : N((int)nxt.size()), LOG(log)
	{
		init(nxt);
	}

	Doubling(const std::vector<int>& nxt,
		const std::vector<T>& value,
		Merge m = Merge(),
		int log = 60)
		: N((int)nxt.size()), LOG(log), merge(m)
	{
		init(nxt, value);
	}

	// k回遷移
	int jump(int v, long long k) const {
		for (int i = 0; i < LOG; ++i) {
			if (k >> i & 1) v = to[i][v];
		}
		return v;
	}

	// value付き k回遷移
	std::pair<int, T> jump_value(int v, long long k) const {
		T res{};
		for (int i = 0; i < LOG; ++i) {
			if (k >> i & 1) {
				res = merge(res, val[i][v]);
				v = to[i][v];
			}
		}
		return { v, res };
	}

	// f(jump(v,k)) が true になる最小 k (存在しなければ -1)
	template<class F>
	long long first_true(int v, long long limit, F f) const {
		T acc{};
		if (f(v, acc)) return 0;

		long long k = 0;

		for (int i = LOG - 1; i >= 0; --i) {
			if (k + (1LL << i) > limit) continue;

			int nv = to[i][v];
			T nacc;
			if constexpr (std::is_same_v<T, DoublingNoValue>) nacc = acc;
			else nacc = merge(acc, val[i][v]);

			if (!f(nv, nacc)) {
				v = nv;
				acc = nacc;
				k += 1LL << i;
			}
		}

		if (k == limit) return -1;
		return k + 1;
	}

private:

	std::vector<std::vector<int>> to;
	std::vector<std::vector<T>> val;
	Merge merge;

	void init(const std::vector<int>& nxt) {
		to.assign(LOG, std::vector<int>(N));
		to[0] = nxt;

		for (int i = 1; i < LOG; ++i) {
			for (int v = 0; v < N; ++v) {
				to[i][v] = to[i - 1][to[i - 1][v]];
			}
		}
	}

	void init(const std::vector<int>& nxt, const std::vector<T>& value) {
		to.assign(LOG, std::vector<int>(N));
		val.assign(LOG, std::vector<T>(N));

		to[0] = nxt;
		val[0] = value;

		for (int i = 1; i < LOG; ++i) {
			for (int v = 0; v < N; ++v) {
				int u = to[i - 1][v];
				to[i][v] = to[i - 1][u];
				val[i][v] = merge(val[i - 1][v], val[i - 1][u]);
			}
		}
	}
};
} // namespace kwm_t::algorithm::search

#endif // KWM_T_ALGORITHM_SEARCH_DOUBLING_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m, q; cin >> n >> m >> q;
	vector<int>l(m), r(m);
	rep(i, m) {
		cin >> l[i] >> r[i];
		l[i]--, r[i]--;
	}
	vector<long long>t(q), x(q);
	vector sh(m, vector<pair<long long, long long>>());
	// t kai ato no a[x]
	rep(i, q) {
		cin >> t[i] >> x[i];
		x[i]--;
		sh[t[i] % m].emplace_back(x[i], i);
		t[i] /= m;
	}
	vector<int>a(n);
	rep(i, n)a[i] = i;
	rep(i, m) {
		for (auto [xx, idx] : sh[i]) {
			x[idx] = a[xx];
		}
		swap(a[l[i]], a[r[i]]);
	}
	kwm_t::algorithm::search::Doubling db(a);
	rep(i, q) {
		auto ans = db.jump(x[i], t[i]);
		cout << ans + 1 << endl;
	}
	return 0;
}