#1190590 (C++23) No.3746 Swap and LIS

• 問題: No.3746 Swap and LIS
• ユーザー: kwm_t
• 提出日時: 2026-09-26 16:46:22
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 62 ms / 2,000 ms
• コード長: 3,467 bytes
• コンパイル時間: 2,431 ms
• コンパイル使用メモリ: 345,468 KB
• 実行使用メモリ: 9,916 KB
• 最終ジャッジ日時: 2026-09-26 16:46:30
• 合計ジャッジ時間: 7,866 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_1

ファイルパターン	結果
sample	AC * 1
other	AC * 22

ソースコード

#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_MATH_ROBINSON_SCHENSTED_HPP
#define KWM_T_MATH_ROBINSON_SCHENSTED_HPP

#include <algorithm>
#include <utility>
#include <vector>

namespace kwm_t::math {

/**
 * @brief Robinson-Schensted 対応により、配列を P-tableau と Q-tableau に変換する。
 *
 * P-tableau は値を保持する半標準 Young tableau、
 * Q-tableau は各要素が元の配列の何番目から挿入されたかを保持する。
 *
 * is_strong が true の場合は lower_bound を用いる。
 * is_strong が false の場合は upper_bound を用いる。
 *
 * 計算量:
 *   O(N * K * log N)
 *
 * @tparam T 要素の型。
 *
 * @param a 入力配列。
 * @param k tableau の最大行数。
 * @param is_strong 挿入時に lower_bound を使用するか。
 *
 * @return
 *   first  : P-tableau。
 *   second : Q-tableau。
 *
 * 制約 / 注意:
 *   - k <= 0 の場合は空の tableau を返す。
 *   - Q-tableau の値は 0-indexed の入力位置。
 *   - is_strong == true の場合は lower_bound、
 *     is_strong == false の場合は upper_bound を使用する。
 *
 * verified:
 *   - https://atcoder.jp/contests/abc468/submissions/77872609
 *   - 上記は嘘解法のためWAです
 */
template <class T>
std::pair<std::vector<std::vector<T>>, std::vector<std::vector<int>>>
robinson_schensted(
	const std::vector<T>& a,
	int k,
	bool is_strong = true
) {
	if (k <= 0) return {};

	std::vector<std::vector<T>> p;
	std::vector<std::vector<int>> q;

	p.reserve(k);
	q.reserve(k);

	for (int i = 0; i < static_cast<int>(a.size()); ++i) {
		T value = a[i];

		for (int row_index = 0; row_index < k; ++row_index) {
			if (row_index == static_cast<int>(p.size())) {
				p.emplace_back();
				q.emplace_back();
			}

			auto& p_row = p[row_index];

			auto it = is_strong
				? std::lower_bound(p_row.begin(), p_row.end(), value)
				: std::upper_bound(p_row.begin(), p_row.end(), value);

			if (it == p_row.end()) {
				p_row.push_back(value);
				q[row_index].push_back(i);
				break;
			}

			std::swap(value, *it);
		}
	}

	return { std::move(p), std::move(q) };
}

} // namespace kwm_t::math

#endif // KWM_T_MATH_ROBINSON_SCHENSTED_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<int>a(n), b(n);
		rep(i, n)cin >> a[i];
		rep(i, n)cin >> b[i];
		vector<int>c(n * 2);
		rep(i, n) {
			c[i * 2 + 0] = max(a[i], b[i]);
			c[i * 2 + 1] = min(a[i], b[i]);
		}

		auto tmp = kwm_t::math::robinson_schensted(c, 2);
		int ans = tmp.first[0].size() + tmp.first[1].size();
		cout << ans << endl;
	}
	return 0;
}