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

• 問題: No.3746 Swap and LIS
• ユーザー: cho435
• 提出日時: 2026-09-25 23:00:18
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 11,921 bytes
• コンパイル時間: 4,429 ms
• コンパイル使用メモリ: 397,812 KB
• 実行使用メモリ: 195,460 KB
• 最終ジャッジ日時: 2026-09-25 23:00:54
• 合計ジャッジ時間: 22,802 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 3 WA * 16 TLE * 3

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>

namespace cho {
struct bit_vector {
	int zeros;
	std::vector<uint64_t> block;
	std::vector<int> count;
	bit_vector() {};
	bit_vector(const int num)
		: zeros(num), block((num >> 6) + 1, 0), count((num >> 6) + 1, 0) {};
	void set(const int i) {
		assert((i >> 6) < (int)block.size());
		block[i >> 6] |= (1ULL << (i & 63));
	}
	bool operator[](int i) const {
		assert((i >> 6) < (int)block.size());
		return (block[i >> 6] >> (i & 63)) & 1;
	}
	void build() {
		for (int i = 1; i < (int)block.size(); i++) {
			count[i] = count[i - 1] + std::popcount(block[i - 1]);
		}
		zeros -= count.back() + std::popcount(block.back());
	}
	int rank1(const int i) const {
		assert((i >> 6) < (int)block.size());
		return count[i >> 6] +
			   std::popcount(block[i >> 6] & ((1ULL << (i & 63)) - 1ULL));
	}
	int rank0(const int i) const {
		return i - rank1(i);
	}
	int rank0() const {
		return zeros;
	}
};

template <typename T, int MAXLOG = 20>
struct wavelet_matrix {
	int n;
	std::array<bit_vector, MAXLOG> bit;
	wavelet_matrix() {};
	wavelet_matrix(const std::vector<T>& v) : n(v.size()) {
		bit.fill(bit_vector(n));
		std::vector<int> left(n), right(n), ord(n);
		std::iota(ord.begin(), ord.end(), 0);
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int idx0 = 0, idx1 = 0;
			for (int i = 0; i < n; i++) {
				if ((v[ord[i]] >> level) & 1) {
					bit[level].set(i);
					right[idx1++] = ord[i];
				} else {
					left[idx0++] = ord[i];
				}
			}
			bit[level].build();
			swap(ord, left);
			for (int i = 0; i < idx1; i++) ord[idx0 + i] = right[i];
		}
	}
	static constexpr int ln() {
		return MAXLOG;
	}
	T k_th_smallest(int l, int r, int k) const {
		assert(0 <= l && l <= r && r <= n);
		assert(0 <= k && k < r - l);
		T res = 0;
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			if (r0 - l0 <= k) {
				l += bit[level].rank0() - l0;
				r += bit[level].rank0() - r0;
				k -= r0 - l0;
				res |= T(1) << level;
			} else {
				l = l0, r = r0;
			}
		}
		return res;
	}
	T k_th_largest(int l, int r, int k) const {
		return k_th_smallest(l, r, r - l - k - 1);
	}
	int freq_count(int l, int r, const T& upper) const {
		assert(0 <= l && l <= r && r <= n);
		assert(T(0) <= upper && upper < T(1) << MAXLOG);
		int ret = 0;
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			if (((upper >> level) & 1)) {
				ret += r0 - l0;
				l += bit[level].rank0() - l0;
				r += bit[level].rank0() - r0;
			} else {
				l = l0, r = r0;
			}
		}
		return ret;
	}
};
}  // namespace cho

namespace cho {
template <class S, auto op, auto e, typename T, int MAXLOG = 20>
struct wm_segtree : public wavelet_matrix<T, MAXLOG> {
	using wm = wavelet_matrix<T, MAXLOG>;
	using wm::bit;
	using wm::n;

	using segtree = atcoder::segtree<S, op, e>;
	std::array<segtree, MAXLOG> seg;

	wm_segtree() {};
	wm_segtree(const std::vector<T>& v) : wm(v) {
		seg.fill(segtree(std::vector<S>(n, e())));
	}
	wm_segtree(const std::vector<T>& v, const std::vector<S>& val) {
		assert(val.size() == v.size());
		n = v.size();
		bit.fill(bit_vector(n));
		std::vector<int> left(n), right(n), ord(n);
		std::iota(ord.begin(), ord.end(), 0);
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int idx0 = 0, idx1 = 0;
			for (int i = 0; i < n; i++) {
				if ((v[ord[i]] >> level) & 1) {
					bit[level].set(i);
					right[idx1++] = ord[i];
				} else {
					left[idx0++] = ord[i];
				}
			}
			bit[level].build();
			swap(ord, left);
			for (int i = 0; i < idx1; i++) ord[idx0 + i] = right[i];
			std::vector<S> tmp(n, e());
			for (int i = 0; i < n; i++) tmp[i] = val[ord[i]];
			seg[level] = segtree(tmp);
		}
	}
	void set(int i, S x) {
		assert(0 <= i && i < n);
		for (int level = MAXLOG - 1; level >= 0; level--) {
			if (bit[level][i]) i += bit[level].rank0() - bit[level].rank0(i);
			else i = bit[level].rank0(i);
			seg[level].set(i, x);
		}
	}
	void add(int i, S x) {
		assert(0 <= i && i < n);
		for (int level = MAXLOG - 1; level >= 0; level--) {
			if (bit[level][i]) i += bit[level].rank0() - bit[level].rank0(i);
			else i = bit[level].rank0(i);
			seg[level].add(i, x);
		}
	}
	void set_vector(const std::vector<S>& val) {
		assert((int)val.size() == n);
		std::array<std::vector<S>, MAXLOG> res;
		res.fill(std::vector<S>(n, e()));
		for (int i = 0; i < n; i++) {
			int nw = i;
			for (int lv = MAXLOG - 1; lv >= 0; lv--) {
				if (bit[lv][nw]) nw += bit[lv].rank0() - bit[lv].rank0(nw);
				else nw = bit[lv].rank0(nw);
				res[lv][nw] = val[i];
			}
		}
		for (int lv = 0; lv < MAXLOG; lv++) seg[lv] = segtree(res[lv]);
	}
	S bottom_k_sum(int l, int r, int k) const {
		assert(0 <= l && l <= r && r <= n);
		assert(0 <= k && k <= r - l);
		if (l == r || k == 0) return e();
		S res = e();
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			if (r0 - l0 <= k) {
				if (l0 < r0) res = op(res, seg[level].prod(l0, r0));
				k -= r0 - l0;
				l += bit[level].rank0() - l0;
				r += bit[level].rank0() - r0;
			} else {
				l = l0, r = r0;
			}
		}
		if (k > 0 && l < r) {
			// check
			res = op(res, seg[0].prod(l, l + k));
		}
		return res;
	}
	S top_k_sum(int l, int r, int k) const {
		assert(0 <= l && l <= r && r <= n);
		assert(0 <= k && k <= r - l);
		if (l == r || k == 0) return e();
		S res = e();
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			int l1 = l + bit[level].rank0() - l0;
			int r1 = r + bit[level].rank0() - r0;
			if (r1 - l1 <= k) {
				if (l1 < r1) res = op(res, seg[level].prod(l1, r1));
				k -= r1 - l1;
				l = l0, r = r0;
			} else {
				l = l1, r = r1;
			}
		}
		if (k > 0 && l < r) {
			// check
			res = op(res, seg[0].prod(r - k, r));
		}
		return res;
	}
	template <class F> std::pair<int, S> max_bottom(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= n);
		assert(f(e()));
		if (l == r) return {0, e()};
		int sz = 0;
		S res = e();
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			if (f(op(res, seg[level].prod(l0, r0)))) {
				sz += r0 - l0;
				res = op(res, seg[level].prod(l0, r0));
				l += bit[level].rank0() - l0;
				r += bit[level].rank0() - r0;
			} else {
				l = l0, r = r0;
			}
		}
		if (l < r) {
			// check
			auto g = [&](S x) {
				return f(op(res, x));
			};
			int lr = std::min(r, seg[0].max_right(l, g));
			sz += lr - l;
			res = op(res, seg[0].prod(l, lr));
		}
		return {sz, res};
	}
	template <class F> std::pair<int, S> min_top(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= n);
		assert(f(e()));
		if (l == r) return {0, e()};
		int sz = 0;
		S res = e();
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			int l1 = l + bit[level].rank0() - l0;
			int r1 = r + bit[level].rank0() - r0;
			if (f(op(res, seg[level].prod(l1, r1)))) {
				sz += r1 - l1;
				res = op(res, seg[level].prod(l1, r1));
				l = l0, r = r0;
			} else {
				l = l1, r = r1;
			}
		}
		if (l < r) {
			// check
			auto g = [&](S x) {
				return f(op(res, x));
			};
			int lr = std::max(r, seg[0].min_left(r, g));
			sz += r - lr;
			res = op(res, seg[0].prod(lr, r));
		}
		return {sz, res};
	}
	S rectangle_sum(int i0, int i1, const T& j0, const T& j1) const {
		assert(0 <= i0 && i0 <= i1 && i1 <= n);
		assert(T(0) <= j0 && j0 <= j1 && j1 <= T(1) << MAXLOG);
		if (i0 == i1 || j0 == j1) return e();
		S res = e();
		auto dfs = [&](auto self, int t, int l, int r, T mn, T mx) -> void {
			if (r <= l || mx <= j0 || j1 <= mn) return;
			if (j0 <= mn && mx <= j1 && t < MAXLOG) {
				res = op(res, seg[t].prod(l, r));
				return;
			}
			assert(t > 0);
			t--;
			int z0 = bit[t].rank0(l), z1 = bit[t].rank0(r);
			T md = mn + (T(1) << t);
			self(self, t, z0, z1, mn, md);
			self(self, t, bit[t].rank0() + l - z0, bit[t].rank0() + r - z1, md,
				 mx);
		};
		dfs(dfs, MAXLOG, i0, i1, 0, T(1) << MAXLOG);
		return res;
	}
};
}  // namespace cho

namespace cho {
template <class S, auto op, auto e, class T = long long> struct rectangle_sum {
	static constexpr int MAX_LOG = 20;	// 要素数1048576-1以下
	int n;
	std::vector<S> data;
	cho::wm_segtree<S, op, e, T, MAX_LOG> wm;
	std::vector<std::pair<T, T>> xy;
	std::vector<T> cy;
	std::vector<int> rev;
	rectangle_sum(const std::vector<T>& x, const std::vector<T>& y)
		: rectangle_sum(x, y, std::vector<S>(x.size(), e())) {};
	rectangle_sum(const std::vector<T>& x,
				  const std::vector<T>& y,
				  const std::vector<S>& raw)
		: n(x.size()), data(n), xy(n), cy(y), rev(n) {
		assert((int)y.size() == n && (int)raw.size() == n);
		std::sort(cy.begin(), cy.end());
		cy.erase(std::unique(cy.begin(), cy.end()), cy.end());
		std::vector<int> ord(n);
		std::iota(ord.begin(), ord.end(), 0);
		std::sort(ord.begin(), ord.end(), [&](int i, int j) {
			if (x[i] == x[j]) return y[i] < y[j];
			return x[i] < x[j];
		});
		std::vector<int> py(n);
		for (int i = 0; i < n; i++) {
			xy[i] = {x[ord[i]], y[ord[i]]};
			data[i] = raw[ord[i]];
			py[i] = y_idx(y[ord[i]]);
			rev[ord[i]] = i;
		}
		wm = cho::wm_segtree<S, op, e, T, MAX_LOG>(py, data);
	};
	int idx(T x, T y) const {
		return std::lower_bound(xy.begin(), xy.end(), std::pair(x, y)) -
			   xy.begin();
	}
	int y_idx(T y) const {
		return std::lower_bound(cy.begin(), cy.end(), y) - cy.begin();
	}
	void set_raw(int i, const S& val) {
		data[i] = val;
		wm.set(i, val);
	}
	void add_raw(int i, const S& val) {
		// wm.add(i, val);
		data[i] = op(data[i], val);
		wm.set(i, data[i]);
	}
	void set(int i, const S& val) {
		set_raw(rev[i], val);
	}
	void add(int i, const S& val) {
		add_raw(rev[i], val);
	}
	S get(int i) const {
		return data[rev[i]];
	}
	void set(T x, T y, S val) {
		int i = idx(x, y);
		assert(i < n && xy[i] == std::pair(x, y));
		set_raw(i, val);
	}
	void add(T x, T y, S val) {
		int i = idx(x, y);
		assert(i < n && xy[i] == std::pair(x, y));
		add_raw(i, val);
	}
	S get(T x, T y) const {
		int i = idx(x, y);
		assert(i < n && xy[i] == std::pair(x, y));
		return data[i];
	}

	// [lx, rx) × [ly, ry)
	int count(T lx, T rx, T ly, T ry) const {
		assert(lx <= rx && ly <= ry);
		if (lx == rx || ly == ry) return 0;
		int i0 = idx(lx, ly), i1 = idx(rx, ly);
		return wm.freq_count(i0, i1, y_idx(ry)) -
			   wm.freq_count(i0, i1, y_idx(ly));
	}
	// 領域 [lx, rx) × [ly, ry) 内の点の総和を取得
	S prod(T lx, T rx, T ly, T ry) const {
		assert(lx <= rx && ly <= ry);
		if (lx == rx || ly == ry) return e();
		return wm.rectangle_sum(idx(lx, ly), idx(rx, ly), y_idx(ly), y_idx(ry));
	}
};
}  // namespace cho

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

ll op(ll a, ll b) {
	return max(a, b);
}
ll e() {
	return 0;
}
using rec_sum = cho::rectangle_sum<ll, op, e, int>;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, n) cin >> b[i];
	rep(i, 0, n) b.push_back(a[i]);
	rep(i, 0, n) a.push_back(b[i]);
	rec_sum rs(a, b);
	int INF = 2e9;
	for (int i = n - 1; i >= 0; i--) {
		vector<ll> v(2);
		rep(lp, 0, 2) {
			ll tmp = 0;
			chmax(tmp, rs.prod(a[i] + 1, INF, b[i] + 1, INF) + 2);
			chmax(tmp, rs.prod(0, a[i] + 1, b[i] + 1, INF) + 1);
			chmax(tmp, rs.prod(a[i] + 1, INF, 0, b[i] + 1) + 1);
			v[lp] = tmp;
			swap(a[i], b[i]);
		}
		rs.set(a[i], b[i], v[0]);
		rs.set(b[i], a[i], v[1]);
	}
	cout << rs.prod(0, INF, 0, INF) << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	cin >> t;
	while (t--) solve();
}