思路：我们把先把所有状态和值用线段树或树状数组记录下来（因为他是连续的区间，相当于一段区间的不同状态的和）再通过二分或者倍增找出这段区间及找出左右端点
1：线段树或者着树状数组维护的有两个，一个是前缀和（不管状态），一个是颜色和就是状态
2：左右端点查找：
一个点对应一个颜色，我们假设从x点查找
左端点查找：从x向左查，如果从1到x有刚好x个点则左端点是0；没有的话再找如果大于x则直接跳过（因为我们查的是左端点），其次如果当前查询的点nxt与x距离（x-nxt）= sum - （tmp+cnt）则跳过（sum是从1到x有多少个满足颜色的点，tmp是在nxt这个点上是否满足的，cnt是之前满足的点个数）这个代码的意思是在nxt~x区间都满足
右端点同理
树状数组代码
点击查看代码
#include <bits/stdc++.h>
const int MAXN = 3e5;
using namespace std;
typedef long long ll;
ll C[MAXN + 10], V[MAXN + 10];
unordered_map<int,int> colTree[MAXN + 10];
ll smTree[MAXN + 10];
ll n,m;
//记录颜色
void add(int x,int y,int z)
{
for(int i = x;i <= n;i += (i&-i))
{
colTree[i][y] += z;
}
}
//记录值
void addv(int x,int y)
{
for(int i = x;i <= n;i += (i&-i))
smTree[i] += y;
}
//计算值
ll query(int x)
{
ll ans = 0;
for(int i = x;i;i -= (i&-i))
ans += smTree[i];
return ans;
}
//算出从1~x有多少个满足的点
ll checksum(int x,set<int>q)
{
ll num = 0;
for(int i = x;i;i -= (i&-i))
{
for(auto c:q)
if(colTree[i][c]!=0)
num += colTree[i][c];
}
return num;
}
//算出左端点
ll checkL(int x,set<int>q)
{
ll sum = checksum(x,q);
if(sum == x)
return 0;
int u = 0;
//倍增
for(u = 1;u <= n;u <<= 1) ;
ll now = 0,cnt = 0;
//nxt = now|u表示下标，例如now = 4，u = 2则nxt表示6
//因为now一旦改变则当前nxt~x这个区间表示都满足条件
//思想类似倍增
for(u >>= 1;u;u >>=1)
{
int nxt = now|u,tmp = 0;
for(auto c:q)
{
if(colTree[nxt][c]!=0)
tmp += colTree[nxt][c];
}
if(nxt > x||x - nxt == sum - tmp-cnt)
continue;
else
{
cnt += tmp;
now = nxt;
}
}
return now + 1;
}
//算出右端点
ll checkR(int x,set<int>q)
{
ll sum = checksum(x,q);
int u;
for(u = 1;u <= n;u <<= 1) ;
ll now = 0,cnt = 0;
for(u >>= 1;u;u >>=1)
{
int nxt = now|u,tmp = 0;
for(auto c:q)
{
if(colTree[nxt][c]!=0)
tmp += colTree[nxt][c];
}
if(nxt < x||nxt - x == tmp+cnt-sum)
{
cnt += tmp;
now = nxt;
}
}
return now;
}
void solve()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
{
cin >> C[i];
add(i,C[i],1);
}
for(int i = 1;i <= n;i ++)
{
cin >> V[i];
addv(i,V[i]);
}
while(m--)
{
ll op,x,y;
cin >> op >> x >> y;
if(op == 1)
{
add(x,C[x],-1);
add(x,y,1);
C[x] = y;
}
else if(op == 2)
{
addv(x,y - V[x]);
V[x] = y;
}
else
{
set<int>q;
bool f = false;
for(int i = 1;i <= y;i ++)
{
int w;
cin >> w;
q.insert(w);
if(C[x] == w)
f = true;
}
if(!f)
{
cout << 0 << '\n';
continue;
}
ll L = checkL(x,q);
ll R = checkR(x,q);
cout << query(R)-query(L) << '\n';
}
}
for (int i = 1; i <= n; i++) colTree[i].clear();
for (int i = 1; i <= n; i++) smTree[i] = 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t;
cin >> t;
while(t--)
solve();
}