我测样例可以过,交上去却是一片紫色。真的不理解了欸。为了方便各位大佬阅读,我加上了注释。请各位大佬帮蒟蒻康康是哪里的问题呀,为什么全是RE,应该不是我数组开小了的问题。
蒟蒻悬赏若干关注(●'◡'●)
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N = 133335;
const int M = 10000;
int n, m;
int col[N];
/// st 一个块的start
/// ed 一个块的end
/// 一个节点的 belong
int st[M], ed[M], bel[M];
unordered_map<int, int> mp[M]; // 储存每一个块的某一个颜色的个数
bitset<N> vis[M]; // 存储每一个块有哪几种颜色
signed main()
{
n = read(), m = read();
int sq = sqrt(n);
// 确定块长
for (int i = 1; i <= sq; i++)
{
st[i] = n / sq * (i - 1) + 1;
ed[i] = n / sq * i;
}
ed[sq] = n;
// 确定点的归属
for (int i = 1; i <= sq; i++)
for (int j = st[i]; j <= ed[i]; j++)
bel[j] = i;
for (int i = 1; i <= sq; i++)
for (int j = st[i]; j <= ed[i]; j++)
{
col[j] = read();
mp[i][col[j]]++;
vis[i][col[j]] = true;
}
for (int i = 1; i <= m; i++)
{
char str = getchar();
int L, R, P, color;
if (str == 'Q')
{
L = read(), R = read();
int bell = bel[L], belr = bel[R];
int res = 0;
// 如果在同一个块中,暴力
if (bell == belr)
{
unordered_map<int, int> mpp;
for (int i = L; i <= R; i++)
{
if (!mpp[col[i]])
res++,
mpp[col[i]]++;
}
cout << res << endl;
continue;
}
else
{
bitset<N> bi;
// 确定整块的颜色个数,使用或
for (int i = bell + 1; i < belr; i++)
bi |= vis[i];
// 确定两端的散块的颜色
for (int i = L; i <= ed[bell]; i++)
bi[col[i]] = true;
for (int i = st[belr]; i <= R; i++)
bi[col[i]] = true;
// 看有多少个 1
cout << bi.count() << endl;
continue;
}
}
else
{
P = read(), color = read();
int belp = bel[P]; // p 属于 belp 这个块
if (!(--mp[belp][col[P]])) // 如果这个块去掉一个颜色就没了这个颜色
vis[belp][col[P]] = false;
col[P] = color; // 更改节点颜色
vis[belp][color] = true;
mp[belp][color]++;
continue;
}
}
return 0;
}