显然，询问的答案即为 \(x\) 所在的极长的满足颜色均在 \(\mathbb{A}\) 内的连续段的权值和。如果我们能维护对颜色的单点修改，以及求出某个位置所在极长连续段的左右端点 \(l,r\)，只需要树状数组即可求出答案。
一个朴素的想法是对每种颜色开一棵线段树，单点修改是平凡的，极长连续段左端点只需要线段树上二分找到最靠右的 \(l\)，使得 \(\mathbb{A}\) 中每种颜色在 \([l,x]\) 的出现次数之和恰好等于 \(x-l+1\)，极长连续段右端点同理。
咱赛时没算这玩意的空间开销有多大，就直接莽了个主席树上去。主席树的话空间复杂度显然为 \(O((n+q)\log n)\)，实现中开了 \(64\) 倍数组。
赛时懒得写线段树上二分的 \(O((n+q)\log n)\) 做法，写了二分套线段树的 \(O(n\log n+q\log^2n)\) 跑过去了。
// Problem: T368285 [GDCPC2023] F-Traveling in Cells
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T368285?contestId=135929
// Memory Limit: 1 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 1e5 + 5;
ll T, n, q, c[N], v[N];
struct BIT {
ll c[N];
void init(ll x) {rep(i, 1, x) c[i] = 0;}
ll lowbit(ll x) {return x & (-x);}
void add(ll x, ll k) {for(; x <= n; x += lowbit(x)) c[x] += k;}
ll ask(ll x) {ll k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
ll Ask(ll l, ll r) {return ask(r) - ask(l - 1);}
}bit;
struct PersSegTree {
ll cnt[N << 6], lc[N << 6], rc[N << 6], rt[N], sz;
void clear() {
rep(i, 1, sz) cnt[i] = lc[i] = rc[i] = 0;
rep(i, 1, n) rt[i] = 0;
sz = 0;
}
ll copy(ll u) {
++sz;
cnt[sz] = cnt[u];
lc[sz] = lc[u];
rc[sz] = rc[u];
return sz;
}
void pushup(ll u) {
cnt[u] = cnt[lc[u]] + cnt[rc[u]];
}
ll insert(ll u, ll l, ll r, ll pos, ll k) {
ll v = copy(u);
if(l == r) {
cnt[v] += k;
return v;
}
ll mid = (l + r) >> 1;
if(pos <= mid) lc[v] = insert(lc[u], l, mid, pos, k);
else rc[v] = insert(rc[u], mid + 1, r, pos, k);
pushup(v);
return v;
}
ll query(ll u, ll l, ll r, ll ql, ll qr) {
if(!u) return 0;
if(ql <= l && r <= qr) return cnt[u];
ll mid = (l + r) >> 1, ans = 0;
if(ql <= mid) ans += query(lc[u], l, mid, ql, qr);
if(qr > mid) ans += query(rc[u], mid + 1, r, ql, qr);
return ans;
}
}psgt;
ll findL(const vector<ll>& vec, ll x) {
ll L = 1, R = x + 1;
auto check = [&](ll M) -> bool {
ll len = x - M + 1, cnt = 0;
for(ll c : vec) cnt += psgt.query(psgt.rt[c], 1, n, M, x);
return cnt == len;
};
while(L < R) {
ll M = (L + R) >> 1;
if(check(M)) R = M;
else L = M + 1;
}
return L;
}
ll findR(const vector<ll>& vec, ll x) {
ll L = x, R = n + 1;
auto check = [&](ll M) -> bool {
ll len = M - x + 1, cnt = 0;
for(ll c : vec) cnt += psgt.query(psgt.rt[c], 1, n, x, M);
return cnt == len;
};
while(L < R) {
ll M = (L + R) >> 1;
if(check(M)) L = M + 1;
else R = M;
}
return L - 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for(cin >> T; T; --T) {
cin >> n >> q;
rep(i, 1, n) cin >> c[i];
rep(i, 1, n) cin >> v[i];
bit.init(n);
psgt.clear();
rep(i, 1, n) bit.add(i, v[i]);
rep(i, 1, n) psgt.rt[c[i]] = psgt.insert(psgt.rt[c[i]], 1, n, i, +1);
while(q--) {
ll op;
cin >> op;
if(op == 1) {
ll x, y;
cin >> x >> y;
psgt.rt[c[x]] = psgt.insert(psgt.rt[c[x]], 1, n, x, -1);
c[x] = y;
psgt.rt[c[x]] = psgt.insert(psgt.rt[c[x]], 1, n, x, +1);
}
else if(op == 2) {
ll x, y;
cin >> x >> y;
bit.add(x, -v[x]);
v[x] = y;
bit.add(x, +v[x]);
}
else {
ll x, k;
cin >> x >> k;
vector<ll> vec(k);
for(ll& i : vec) cin >> i;
ll L = findL(vec, x), R = findR(vec, x);
cout << bit.Ask(L, R) << endl;
}
}
}
return 0;
}