题意
给一棵树，每个节点有一个权值，并且权值是一个排列。接下来有多次操作，每次操作要么是交换两个节点权值，要么是询问一个权值区间 \([L,R]\)， 判断是否存在树上的一个路径，使得路径上的权值恰好都在这个区间里
分析
由于询问的是树上的一个路径，联想到了树上莫队中对路径的处理。
这里引用一下别人博客里对树上莫队的介绍，原博客地址(https://www.cnblogs.com/Arson1st/p/17761476.html)
总之，树上莫队利用括号序，找到路径两个端点的对应区间，会满足这样一个性质:恰好在路径里的点，在区间中出现1次，不在路径里的点，在区间中出现2次，所以树上莫队可以记录每个点出现次数判断一个点是应该被加入还是删除。
在这题里面，如果存在一个路径满足路径上的权值恰好构成 \([L,R]\)，那么也用括号序，不在路径上的点会在区间里出现2次，在的点出现1次，天然的就会想到利用异或消除两次的点的影响。
所以可以给排列权值，每个点随机化赋值，那么如果一个路径上满足权值恰好构成 \([L, R]\)，则对应括号序的区间异或和，等于 \([L,R]\) 权值对应的异或和(这个显然可以用一个前缀异或和 \(O(1)\)得到)
所以，现在问题相当于变成，在括号序上找一个区间，满足异或和等于一个指定的值。正着给定路径端点，知道对应区间，但是现在逆过来，就有点不知道怎么找了，这里是队友给的思路。
再维护一下每个权值，对应的括号序，相当于找区间 \([L, R]\) 里最小的最大的括号序，加个线段树最值查询就好了。具体实现的话，我是把括号序里面的 \(in[i]\) 和 \(out[i]\)(\(in\)记录每个节点入栈的dfs序，也就是先序遍历顺序, \(out\)记录每个点退栈的dfs序) 分开，以排列的权值为下标，记录每个权值对应的节点的\(in\) 和 \(out\), 分别存两个线段树，支持查询最值。那么可能的合法括号序区间即为 \([min(in[i]), min(out[i])]\) 和 \([min(in[i], max(in[i]))]\) (这两个区间其实就相当于树上莫队的两种情况)，查询这两个区间对应的异或和是不是恰好等于需要的异或和即可。
然后操作一交换两个权值，只要把三个线段树中，对应两个节点的内容交换一下即可，当然实现上写个单点赋值修改就好了。因为总的需要用到线段树的操作就是单点修改，区间异或和，最大值最小值查询，所以可以直接把线段树封装到结构体里这些功能全实现，开三个线段树。
下面是代码，注意里面三个vector, v1维护每个权值对应的节点的in[u]，v2维护对应节点的权值的in[v]， v3维护每个dfs时间戳对应的随机化权值是多少。然后交换的时候，这三个数组也要对应交换。
代码里面三个线段树，两个是用来找询问区间对应的dfs序最值，这两个的线段树下标是权值，值是dfs时间戳，第三个线段树的下标是dfs时间戳，值是对应节点的权值的随机化权值。其他的详见代码:
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 4e5 + 10;
const int mod = 998244353;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int val[maxn], L[maxn], R[maxn], p[maxn], ncnt = 0;
int xorsum[maxn];
vector<int> G[maxn];
vector<int> v1, v2, v3;
struct SegmentTree {
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
struct Node {
int mn, mx, sum;
};
vector<Node> t;
SegmentTree(int n) { t.resize((n + 1) << 2); }
void push_up(int rt) {
t[rt].sum = t[ls].sum ^ t[rs].sum;
t[rt].mn = min(t[ls].mn, t[rs].mn);
t[rt].mx = max(t[ls].mx, t[rs].mx);
}
void build(int rt, int l, int r, vector<int>& arr) {
if (l == r) {
t[rt].sum = t[rt].mx = t[rt].mn = arr[l];
return;
}
build(ls, l, mid, arr);
build(rs, mid + 1, r, arr);
push_up(rt);
}
void modify(int rt, int l, int r, int pos, int k) {
if (l == r) {
t[rt].sum = t[rt].mn = t[rt].mx = k;
return;
}
if (pos <= mid)
modify(ls, l, mid, pos, k);
else
modify(rs, mid + 1, r, pos, k);
push_up(rt);
}
int query(int rt, int l, int r, int p, int q) {
if (q < l || p > r)
return 0;
if (p <= l && r <= q)
return t[rt].sum;
return (query(ls, l, mid, p, q) ^ query(rs, mid + 1, r, p, q));
}
int querymn(int rt, int l, int r, int p, int q) {
if (q < l || p > r)
return inf;
if (p <= l && r <= q)
return t[rt].mn;
return min(querymn(ls, l, mid, p, q), querymn(rs, mid + 1, r, p, q));
}
int querymx(int rt, int l, int r, int p, int q) {
if (q < l || p > r)
return 0;
if (p <= l && r <= q)
return t[rt].mx;
return max(querymx(ls, l, mid, p, q), querymx(rs, mid + 1, r, p, q));
}
};
void dfs(int u, int f) {
L[u] = ++ncnt;
v3[ncnt] = val[p[u]];
v1[p[u]] = ncnt, v2[p[u]] = ncnt;
for (auto v : G[u]) {
if (v == f)
continue;
dfs(v, u);
}
R[u] = ++ncnt;
}
void solve() {
v1.clear(), v2.clear(), v3.clear();
ncnt = 0;
int n;
cin >> n;
v1.resize(n + 1), v2.resize(n + 1), v3.resize(2 * n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[i];
val[p[i]] = rng();
G[i].clear();
}
for (int i = 1; i <= n; i++)
xorsum[i] = xorsum[i - 1] ^ val[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, 0);
SegmentTree segL(n), segR(n), segsum(2 * n);
segL.build(1, 1, n, v1);
segR.build(1, 1, n, v2);
segsum.build(1, 1, 2 * n, v3);
int m;
cin >> m;
while (m--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
if (x == y) continue;
int p1 = v1[p[x]], p2 = v1[p[y]];
segL.modify(1, 1, n, p[x], p2);
segL.modify(1, 1, n, p[y], p1);
p1 = v2[p[x]], p2 = v2[p[y]];
segR.modify(1, 1, n, p[x], p2);
segR.modify(1, 1, n, p[y], p1);
p1 = val[p[x]], p2 = val[p[y]];
segsum.modify(1, 1, 2 * n, L[x], p2);
segsum.modify(1, 1, 2 * n, R[x], p2);
segsum.modify(1, 1, 2 * n, L[y], p1);
segsum.modify(1, 1, 2 * n, R[y], p1);
swap(v1[p[x]], v1[p[y]]);
swap(v2[p[x]], v2[p[y]]);
swap(p[x], p[y]);
} else {
int tar = xorsum[y] ^ xorsum[x - 1];
int mnin = segL.querymn(1, 1, n, x, y),
mxin = segL.querymx(1, 1, n, x, y);
int mnout = segR.querymn(1, 1, n, x, y);
int flag = 0;
if (mnin <= mnout)
flag |= (segsum.query(1, 1, 2 * n, mnin, mnout) == tar);
if (mnin <= mxin)
flag |= (segsum.query(1, 1, 2 * n, mnin, mxin) == tar);
if (flag) cout << "Yes\n";
else cout << "No\n";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}