我本来是nloglog的，cf用树状数组和神秘优化卡过去了。

后面想了一下线段树上二分的写法，应该是nlogn的，但是发现cf上竟然过不了，还得加点什么神秘优化才能刚刚卡过去。

但是洛谷是能过得，最慢的耗时3.30s左右,求大佬们解答？ 还是说这是我没用树状数组的缘故？还是说cf评测机有问题

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
#define int long long
#define endl '\n'
#define lc u<<1
#define rc u<<1|1
#define mid ((l+r)>>1)
const int N=1e5+10;
int ls[N*45],rs[N*45],sum[N*45];
int root[N],tot;
int l1,r1,l2,r2;

int val[N*4];
int e;
int a[N];
int c[N],v[N];
int n,m;
int len;
void pushup(int u){
    val[u]=val[lc]+val[rc];
}
void build(int u,int l,int r){
    if(l==r){
        val[u]=v[l];return;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(u);
}
void change(int u,int l,int r,int x,int k){
    if(l==r){
        val[u]=k;return;
    }
    if(x<=mid) change(lc,l,mid,x,k);
    else change(rc,mid+1,r,x,k);
    pushup(u);
}
void update(int &u,int v,int l,int r,int x,int k){
    u=++tot;
    ls[u]=ls[v],rs[u]=rs[v],sum[u]=sum[v]+k;
    if(l==r) return;
    if(x<=mid) update(ls[u],ls[v],l,mid,x,k);
    else update(rs[u],rs[v],mid+1,r,x,k);
}
int que(int u,int l,int r,int x,int y){
    if(x<=l&&r<=y) return val[u];
    int num=0;
    if(x<=mid) num+=que(lc,l,mid,x,y);
    if(y>mid) num+=que(rc,mid+1,r,x,y);
    return num;
}
int query(int v,int l,int r,int x,int y){
    if(!v) return 0;
    if(x<=l&&r<=y) return sum[v];
    int num=0;
    if(x<=mid) num+=query(ls[v],l,mid,x,y);
    if(y>mid) num+=query(rs[v],mid+1,r,x,y);
    return num;
}
void askr(int &l,int &r){
    if(l+1==r) return;
    int m=(l+r)>>1;
    int num=0;
    for(int i=1;i<=len;++i) num+=query(root[a[i]],1,n,e,m);
    if(num==m-e+1){
        l=m;
        askr(l,r);
    }
    else if(num<m-e+1){
        r=m;
        askr(l,r);
    }
}
void askl(int &l,int &r){
    //cout<<l<<' '<<r<<endl;
    if(l+1==r) return;
    int m=(l+r)>>1;
    int num=0;
    for(int i=1;i<=len;++i) num+=query(root[a[i]],1,n,m,e);
    //cout<<m<<' '<<num<<endl;
    if(num==e-m+1){
        r=m;
        //if(l==r) return;
        askl(l,r);
    }
    else if(num<e-m+1){
        l=m;
        //if(l==r) return;
        askl(l,r);
    }
}
//  while(l1+1<r1){
//     int m=(l1+r1)>>1;
//     int num=0;
//     for(int i=1;i<=k;++i) num+=query(root[a[i]],1,n,m,x);
//     if(num<x-m+1) l1=m;
//     else r1=m;
// }
void solve(){
    tot=0;
	cin>>n>>m;
    for(int i=1;i<=n;++i) root[i]=0;
    for(int i=1;i<=n;++i){
        cin>>c[i];
        update(root[c[i]],root[c[i]],1,n,i,1);
    }
    for(int i=1;i<=n;++i) cin>>v[i];
    build(1,1,n);
    for(int i=1;i<=m;++i){
        int op;cin>>op;
        if(op==1){
            int p,x;cin>>p>>x;
            update(root[c[p]],root[c[p]],1,n,p,-1);
            c[p]=x;
            update(root[c[p]],root[c[p]],1,n,p,1);
        }
        else if(op==2){
            int p,x;cin>>p>>x;
            change(1,1,n,p,x);
            v[p]=x;
        }
        else{
            cin>>e>>len;
            for(int i=1;i<=len;++i) cin>>a[i];
            l1=0,r1=e+1;
            askl(l1,r1);
            l2=e-1,r2=n+1;
            askr(l2,r2);
            //cout<<endl;
            //cout<<r1<<' '<<l2<<endl;
            cout<<que(1,1,n,r1,l2)<<endl;
            //cout<<r1<<' '<<l2<<endl;
        }
        //cout<<1<<endl;
    }

}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
    cin>>_;
	while(_--){
		solve();
	}
	return 0;
}