spj 代码来自 loj：

// Author: HeRaNO
#include "testlib.h"

int a[1 << 12], b[1 << 12], pans[1 << 12];
std::pair<int, int> mx[1 << 13], mn[1 << 13];

inline void BuildTree(int u, int l, int r)
{
	if (l + 1 == r)
	{
		mn[u] = mx[u] = {a[l], l};
		return ;
	}
	int m = l + r >> 1;
	BuildTree(u << 1, l, m);
	BuildTree(u << 1 | 1, m, r);
	mx[u] = std::max(mx[u << 1], mx[u << 1 | 1]);
	mn[u] = std::min(mn[u << 1], mn[u << 1 | 1]);
	return ;
}

inline void modify(int u, int x, int v, int pl, int pr)
{
	if (pl + 1 == pr)
	{
		mn[u] = mx[u] = {v, x};
		return ;
	}
	int m = pl + pr >> 1;
	if (x < m) modify(u << 1, x, v, pl, m);
	else modify(u << 1 | 1, x, v, m, pr);
	mx[u] = std::max(mx[u << 1], mx[u << 1 | 1]);
	mn[u] = std::min(mn[u << 1], mn[u << 1 | 1]);
	return ;
}

inline std::pair<int, int> qmax(int u, int l, int r, int pl, int pr)
{
	if (l == pl && r == pr) return mx[u];
	int m = pl + pr >> 1;
	if (r <= m) return qmax(u << 1, l, r, pl, m);
	else if (m <= l) return qmax(u << 1 | 1, l, r, m, pr);
	return std::max(qmax(u << 1, l, m, pl, m), qmax(u << 1 | 1, m, r, m, pr));
}

inline std::pair<int, int> qmin(int u, int l, int r, int pl, int pr)
{
	if (l == pl && r == pr) return mn[u];
	int m = pl + pr >> 1;
	if (r <= m) return qmin(u << 1, l, r, pl, m);
	else if (m <= l) return qmin(u << 1 | 1, l, r, m, pr);
	return std::min(qmin(u << 1, l, m, pl, m), qmin(u << 1 | 1, m, r, m, pr));
}

inline void dfs(int u, int l, int r)
{
	if (l + 1 == r) { pans[l] = mx[u].first; return ; }
	int m = l + r >> 1;
	dfs(u << 1, l, m); dfs(u << 1 | 1, m, r);
	return ;
}

int main(int argc, char *argv[])
{
	registerTestlibCmd(argc, argv);
	int n = inf.readInt();
	for (int i = 0; i < n; i++)
		a[i] = inf.readInt();
	for (int i = 0; i < n; i++)
		b[i] = inf.readInt();
	BuildTree(1, 0, n);
	int Q = ouf.readInt(1, 300000);
	for (int i = 1; i <= Q; i++)
	{
		int l = ouf.readInt(1, n);
		int r = ouf.readInt(1, n);
		if (l > r)
			quitf(_wa, "l > r on operation #%d", i);
		--l;
		std::pair<int, int> mxInfo = qmax(1, l, r, 0, n);
		std::pair<int, int> mnInfo = qmin(1, l, r, 0, n);
		modify(1, mxInfo.second, mnInfo.first, 0, n);
		modify(1, mnInfo.second, mxInfo.first, 0, n);
	}
	dfs(1, 0, n);
	for (int i = 0; i < n; i++)
		if (b[i] != pans[i])
			quitf(_wa, "answer differ on position %d", i + 1);
	quitf(_ok, "ok");
	return 0;
}