@[midsummer_zyl](/user/1025321)
我也是分块，看一下我的代码吧
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = (int)sqrt(N) + 5;
int n, m, q, siz, a[N], c[N << 1], L[N], R[N], pos[N], x[N], y[N], z[N], tot;
char opt[N];
vector<vector<short>> s;
inline int query(int l, int r, int id) {
int ans = 0;
if (pos[l] == pos[r]) {
for (int i = l; i <= r; i++)
ans += (a[i] == c[id]);
return ans;
}
for (int i = l; i <= R[pos[l]]; i++)
ans += (a[i] == c[id]);
for (int i = pos[l] + 1; i <= pos[r] - 1; i++)
ans += s[i][id];
for (int i = L[pos[r]]; i <= r; i++)
ans += (a[i] == c[id]);
return ans;
}
int main() {
scanf("%d %d", &n, &q);
siz = sqrt(n), m = (n + siz - 1) / siz;
for (int i = 1; i <= m; i++)
L[i] = R[i - 1] + 1, R[i] = i * siz;
R[m] = n;
for (int i = 1; i <= m; i++)
for (int j = L[i]; j <= R[i]; j++)
pos[j] = i;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), c[++tot] = a[i];
for (int i = 1; i <= q; i++) {
scanf(" %c", &opt[i]);
if (opt[i] == 'C') {
scanf("%d %d", &x[i], &y[i]);
c[++tot] = y[i];
} else
scanf("%d %d %d", &x[i], &y[i], &z[i]);
}
sort(c + 1, c + tot + 1);
int orz = unique(c + 1, c + tot + 1) - c - 1;
tot = orz;
s = vector<vector<short>>(m + 5, vector<short>(tot + 5));
for (int i = 1; i <= n; i++) {
int id = lower_bound(c + 1, c + tot + 1, a[i]) - c;
s[pos[i]][id]++;
}
for (int i = 1; i <= q; i++)
if (opt[i] == 'C') {
int id = lower_bound(c + 1, c + tot + 1, a[x[i]]) - c;
s[pos[x[i]]][id]--;
a[x[i]] = y[i];
id = lower_bound(c + 1, c + tot + 1, a[x[i]]) - c;
s[pos[x[i]]][id]++;
} else {
int id = lower_bound(c + 1, c + tot + 1, z[i]) - c;
if (z[i] != c[id])
puts("0");
else
printf("%d\n", query(x[i], y[i], id));
}
return 0;
}
by _zhy @ 2024-01-06 15:38:40
@[midsummer_zyl](/user/1025321) cqbz的？
by _zhy @ 2024-01-06 15:39:45
@[_zhy](/user/476921)
是，能找一下错误吗？
by midsummer_zyl @ 2024-01-06 15:42:12
~~这题不是莫队吗~~
by hytallenxu @ 2024-01-06 15:43:23
学长？
by midsummer_zyl @ 2024-01-06 15:44:03
@[midsummer_zyl](/user/1025321) 别开快读了
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N], L[N], R[N], b[N];
int tag[N], bel[N];
inline void update(int l, int r) {
int p = bel[l]; a[l] = r;
for (int i = L[p]; i <= R[p]; ++i)
b[i] = a[i];
sort(b + L[p], b + R[p] + 1);
}
inline int solve(int l, int r, int k) {
int ans = 0, p = bel[l], q = bel[r];
if(p == q) {
for (int i = l; i <= r; ++i)
if(a[i] == k)
ans++;
return ans;
}
for (int i = l; i <= min(r, R[p]); ++i)
if(a[i] == k)
ans++;
for (int i = L[q]; i <= r; ++i)
if(a[i] == k)
ans++;
for (int i = p + 1; i < q; ++i) {
int lv = lower_bound(b + L[i], b + R[i] + 1, k) - b;
int rv = lower_bound(b + L[i], b + R[i] + 1, k + 1) - b - 1;
ans += rv - lv + 1;
}
return ans;
}
inline int read() {
int f = 1, s = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
s = s * 10 + c - '0';
c = getchar();
}
return f * s;
}
signed main() {
int n = read(), m = read();
int siz = sqrt(n), blo = (n + siz - 1) / siz;
for (int i = 1; i <= blo; ++i) {
L[i] = (i - 1) * siz + 1;
R[i] = min(n, i * siz);
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]); b[i] = a[i];
bel[i] = (i - 1) / siz + 1;
}
for (int i = 1; i <= blo; ++i)
sort(b + L[i], b + R[i] + 1);
for (int i = 1; i <= m; ++i) {
char x; scanf(" %c", &x);
if(x == 'Q') {
int l, r, k;
scanf("%lld %lld %lld", &l, &r, &k);
printf("%lld\n", solve(l, r, k));
} else {
int l, r;
scanf("%lld %lld", &l, &r);
update(l, r);
}
}
return 0;
}
by _zhy @ 2024-01-06 15:54:04
@[_zhy](/user/476921) 谢谢学长！
by midsummer_zyl @ 2024-01-06 15:55:22
@[hytallenxu](/user/726098) ~~莫队不是分块吗~~
by Flying_hq @ 2024-01-06 16:25:31
@[midsummer_zyl](/user/1025321) 我要找微信告状
by XiangXunYi @ 2024-01-29 14:20:06
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int V = 2e5 + 5;
int cnt[V], a[N], ans[N];
int n, m, cntq, cntr, cur, siz;
vector<int> pool;
struct node{
int l, r, t, bel, id, q;
bool operator < (const node & o) const {
if(l / siz == o.l / siz){
if(r / siz == o.r /siz) return t < o.t;
else if(l / siz & 1) return r > o.r; else return r < o.r;
}
else return l< o.l;
}
}qq[N],qr[N];
inline void add(int i){
cnt[i]++;
}
inline void del(int i){
cnt[i]--;
}
inline void update(int i,int t){
if(qq[i].l <= qr[t].l && qr[t].l <= qq[i].r){
del(a[qr[t].l]);
add(qr[t].r);
}
swap(a[qr[t].l], qr[t].r);
}
int main(){
// freopen("librarian.in","r",stdin);
// freopen("librarian.out","w",stdout);
scanf("%d %d", &n, &m);
siz = pow(n,0.66);
for(int i = 1; i <= n ; i++) scanf("%d", &a[i]), pool.push_back(a[i]);
for(int i = 1; i <= m ; i++){
char op[5];
int l, r;
scanf("%s%d%d",op,&l,&r);
if(op[0] == 'Q'){
int q;
scanf("%d", &q);
qq[++cntq].l = l;
qq[cntq].r = r;
qq[cntq].id = cntq;
qq[cntq].t =cntr;
qq[cntq].q = q;
pool.push_back(q);
}
else {
pool.push_back(r);
qr[++cntr].l = l;
qr[cntr].r = r;
}
}
int l = 1, r = 0, t = 0;
sort(pool.begin(), pool.end());
pool.erase(unique(pool.begin(), pool.end()), pool.end());
for(int i = 1; i <= n; i++) a[i] = lower_bound(pool.begin(), pool.end(), a[i]) - pool.begin();;
for(int i = 1; i <= cntr; i++) qr[i].r = lower_bound(pool.begin(), pool.end(), qr[i].r) - pool.begin();
for(int i = 1; i <= cntq; i++) qq[i].q = lower_bound(pool.begin(), pool.end(), qq[i].q) - pool.begin();
sort(qq + 1 , qq + 1 + cntq);
for(int i = 1; i <= cntq; i++){
while(l < qq[i].l) del(a[l++]);
while(l > qq[i].l) add(a[--l]);
while(r < qq[i].r) add(a[++r]);
while(r > qq[i].r) del(a[r--]);
while(t < qq[i].t) update(i, ++t);
while(t > qq[i].t) update(i, t--);
ans[qq[i].id] = cnt[qq[i].q];
}
for(int i = 1; i <= cntq; i++) printf("%d\n",ans[i]);
}
@[_zhy](/user/476921) @[midsummer_zyl](/user/1025321) ###cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int V = 2e5 + 5;
int cnt[V], a[N], ans[N];
int n, m, cntq, cntr, cur, siz;
vector<int> pool;
struct node{
int l, r, t, bel, id, q;
bool operator < (const node & o) const {
if(l / siz == o.l / siz){
if(r / siz == o.r /siz) return t < o.t;
else if(l / siz & 1) return r > o.r; else return r < o.r;
}
else return l< o.l;
}
}qq[N],qr[N];
inline void add(int i){
cnt[i]++;
}
inline void del(int i){
cnt[i]--;
}
inline void update(int i,int t){
if(qq[i].l <= qr[t].l && qr[t].l <= qq[i].r){
del(a[qr[t].l]);
add(qr[t].r);
}
swap(a[qr[t].l], qr[t].r);
}
int main(){
// freopen("librarian.in","r",stdin);
// freopen("librarian.out","w",stdout);
scanf("%d %d", &n, &m);
siz = pow(n,0.66);
for(int i = 1; i <= n ; i++) scanf("%d", &a[i]), pool.push_back(a[i]);
for(int i = 1; i <= m ; i++){
char op[5];
int l, r;
scanf("%s%d%d",op,&l,&r);
if(op[0] == 'Q'){
int q;
scanf("%d", &q);
qq[++cntq].l = l;
qq[cntq].r = r;
qq[cntq].id = cntq;
qq[cntq].t =cntr;
qq[cntq].q = q;
pool.push_back(q);
}
else {
pool.push_back(r);
qr[++cntr].l = l;
qr[cntr].r = r;
}
}
int l = 1, r = 0, t = 0;
sort(pool.begin(), pool.end());
pool.erase(unique(pool.begin(), pool.end()), pool.end());
for(int i = 1; i <= n; i++) a[i] = lower_bound(pool.begin(), pool.end(), a[i]) - pool.begin();;
for(int i = 1; i <= cntr; i++) qr[i].r = lower_bound(pool.begin(), pool.end(), qr[i].r) - pool.begin();
for(int i = 1; i <= cntq; i++) qq[i].q = lower_bound(pool.begin(), pool.end(), qq[i].q) - pool.begin();
sort(qq + 1 , qq + 1 + cntq);
for(int i = 1; i <= cntq; i++){
while(l < qq[i].l) del(a[l++]);
while(l > qq[i].l) add(a[--l]);
while(r < qq[i].r) add(a[++r]);
while(r > qq[i].r) del(a[r--]);
while(t < qq[i].t) update(i, ++t);
while(t > qq[i].t) update(i, t--);
ans[qq[i].id] = cnt[qq[i].q];
}
for(int i = 1; i <= cntq; i++) printf("%d\n",ans[i]);
}
by CQBZ_CHECK @ 2024-01-29 14:21:22