（代码比较长，前面是快读之类的，建议从 namespace Solution 看起（
```cpp
#include <iostream>
#include <streambuf>
#include <fstream>
#include <cstring>
#include <algorithm>
namespace AKA
{
#if __cplusplus >= 201103L
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using llrg = __int128_t;
using ullrg = __uint128_t;
using dbl = double;
using ldbl = long double;
#else
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128_t llrg;
typedef __uint128_t ullrg;
typedef double dbl;
typedef long double ldbl;
#endif
} // namespace AKA
namespace IO
{
using namespace AKA;
std::streambuf* inbuf, *outbuf;
char ibuf[1 << 23 | 1], *i1 = ibuf, *i2 = ibuf;
char outstk[105];
int top = 0;
inline char gc() { return (i1 == i2 && (i2 = (i1 = ibuf) + inbuf->sgetn(ibuf, 1 << 23), i1 == i2) ? EOF : *i1++); }
inline void pc(char x) { outbuf->sputc(x); }
inline int iget() { int x = 0; bool f = false; char c = gc(); while (c < '0' || c > '9') { f |= c == '-'; c = gc(); } while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = gc(); } return f ? -x : x; }
inline void ipr(int x) { if (x == 0) { pc('0'); return ; } if (x < 0) { pc('-'); x = -x; } top = 0; while (x) { outstk[top++] = x % 10 + 48; x /= 10; } while (top--) { pc(outstk[top]); } }
inline void iwsp(int x) { ipr(x); pc(' '); }
inline void iwln(int x) { ipr(x); pc('\n'); }
inline ll llget() { ll x = 0; bool f = false; char c = gc(); while (c < '0' || c > '9') { f |= c == '-'; c = gc(); } while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = gc(); } return f ? -x : x; }
inline void llpr(ll x) { if (x == 0) { pc('0'); return ; } if (x < 0) { pc('-'); x = -x; } top = 0; while (x) { outstk[top++] = x % 10 + 48; x /= 10; } while (top--) { pc(outstk[top]); } }
inline void llwsp(ll x) { llpr(x); pc(' '); }
inline void llwln(ll x) { llpr(x); pc('\n'); }
inline ull ullget() { ll x = 0; bool f = false; char c = gc(); while (c < '0' || c > '9') { f |= c == '-'; c = gc(); } while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = gc(); } return f ? -x : x; }
inline void ullpr(ull x) { if (x == 0) { pc('0'); return ; } if (x < 0) { pc('-'); x = -x; } top = 0; while (x) { outstk[top++] = x % 10 + 48; x /= 10; } while (top--) { pc(outstk[top]); } }
inline void ullwsp(ull x) { ullpr(x); pc(' '); }
inline void ullwln(ull x) { ullpr(x); pc('\n'); }
inline void spr(const char* s) { char* t = const_cast<char*>(s); while (*t && (pc(*t++), true)) {} }
inline void swsp(const char* s) { spr(s); pc(' '); }
inline void swln(const char* s) { spr(s); pc('\n'); }
template<typename _Tp> inline void iget(_Tp& x) { x = 0; bool f = false; char c = gc(); while (c < '0' || c > '9') { f |= c == '-'; c = gc(); } while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = gc(); } f && (x = -x); }
template<typename _Tp, typename ... Args> inline void iget(_Tp& x, Args& ... args) { iget(x), iget(args ...); }
template<typename _Tp> inline void pr(_Tp x) { if (x == 0) { pc('0'); return ; } if (x < 0) { pc('-'); x = -x; } top = 0; while (x) { outstk[top++] = x % 10 + 48; x /= 10; } while (top--) { pc(outstk[top]); } }
template<typename _Tp, typename ... Args> inline void pr(_Tp x, Args ... args) { pr(x), pr(args ...); }
template<typename _Tp> inline void wsp(_Tp x) { pr(x), pc(' '); }
template<typename _Tp, typename ... Args> inline void wsp(_Tp x, Args ... args) { wsp(x), wsp(args ...); }
} // namespace IO
#include <cmath>
namespace Solution
{
#ifndef ONLINE_JUDGE
std::ifstream cin;
std::ofstream cout;
#else
using std::cin;
using std::cout;
#endif
using namespace AKA;
using IO::gc; using IO::pc;
using IO::iget; using IO::ipr; using IO::iwsp; using IO::iwln;
using IO::llget; using IO::llpr; using IO::llwsp; using IO::llwln;
using IO::ullget; using IO::ullwsp; using IO::ullwln;
using IO::spr; using IO::swsp; using IO::swln;
using IO::pr; using IO::wsp;
#define flp(name, lpst, lped) for (int name = lpst, name##end = lped; name <= name##end; ++name)
#define plf(name, lpst, lped) for (int name = lpst, name##end = lped; name >= name##end; --name)
constexpr int maxn = 2e6 + 5;
struct QAQstion
{
int l, r, ver, id;
} qaqs[maxn];
struct Modify
{
int pos, val;
} mdf[maxn];
int qaqcnt = 0, mcnt = 0, ans, now;
int a[maxn], bel[maxn], cnt[maxn], res[maxn];
inline void add(int pos)
{
ans += !cnt[a[pos]]++;
}
inline void del(int pos)
{
ans -= !--cnt[a[pos]];
}
inline void upd(int i)
{
if (qaqs[i].l <= mdf[now].pos && mdf[now].pos <= qaqs[i].r)
{
if ((--cnt[a[mdf[now].pos]]) == 0)
{
--ans;
}
if ((++cnt[mdf[now].val]) == 1)
{
++ans;
}
}
std::swap(mdf[now].val, a[mdf[now].pos]);
}
void main(void)
{
std::ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
cin.open("main.in"), cout.open("main.out");
IO::inbuf = cin.rdbuf(); IO::outbuf = cout.rdbuf();
#else
#if __cplusplus >= 201103L
cin.tie(nullptr); cout.tie(nullptr);
#else
cin.tie(NULL); cout.tie(NULL);
#endif
IO::inbuf = cin.rdbuf(); IO::outbuf = cout.rdbuf();
#endif
int n = iget(), General_Q = iget();
flp (i, 1, n)
{
a[i] = iget();
}
flp (i, 1, General_Q)
{
char c;
while ((c = gc()) != 'Q' && c != 'R') {}
if (c == 'Q')
{
qaqs[++qaqcnt].l = iget(), qaqs[qaqcnt].r = iget();
qaqs[qaqcnt].id = qaqcnt, qaqs[qaqcnt].ver = mcnt;
}
else
{
// auto& M = mdf[++mcnt];
// iget(M.pos, M.val);
mdf[++mcnt].pos = iget(), mdf[mcnt].val = iget();
}
}
// int len = std::ceil(std::exp((std::log(n) + std::log(mcnt)) / 3));
int len = std::pow(n, 0.666);
flp (i, 1, qaqcnt)
{
bel[i] = i / len;
}
std::sort(qaqs + 1, qaqs + qaqcnt + 1, [](const auto& x, const auto& y)
{
// if (bel[x.l] != bel[y.l])
// {
// return x.l < y.l;
// }
// if (bel[x.r] != bel[y.r])
// {
// return (bel[x.l] & 1) ? x.r > y.r : x.r < y.r;
// }
// return (bel[x.r] & 1) ? x.ver > y.ver : x.ver < y.ver;
return (bel[x.l] ^ bel[y.l]) ? (x.l < y.l) : ((bel[x.r] ^ bel[y.r]) ? ((bel[x.l] & 1) ? (bel[x.r] < bel[y.r]) : (bel[x.r] > bel[y.r])) : x.ver < y.ver);
});
int l = 1, r = 0;
now = 0;
flp (i, 1, qaqcnt)
{
// std::cerr << i << "\n";
while (r < qaqs[i].r) { add(++r); }
while (l > qaqs[i].l) { add(--l); }
while (r > qaqs[i].r) { del(r--); }
while (l < qaqs[i].l) { del(l++); }
while (now < qaqs[i].ver) { ++now, upd(i); }
while (now > qaqs[i].ver) { upd(i), --now; }
res[qaqs[i].id] = ans;
}
flp (i, 1, qaqcnt) { iwln(res[i]); }
#ifndef ONLINE_JUDGE
cin.close(); cout.close();
#endif
}
} // namespace Solution
int main(void)
{
Solution::main();
return 0;
}
```
by BootsH @ 2022-03-20 09:02:17
我的。
```
#include <bits/stdc++.h>
struct n_t{int l,r,k,t;}x[133533];int L=1,R,t,ans,N,M,s,size,a[133533],
as[133533],b[133533],cnt[1000009],pos[133533],prev[133533],now[133533];
char op[2];
bool cmp(n_t a,n_t b){
if(a.l/size!=b.l/size)return a.l/size<b.l/size;
if(a.r/size!=b.r/size)return a.r/size<b.r/size;
return a.t<b.t;
}
void del(int p) {if(cnt[p]==1) ans--;cnt[p]--;}
void add(int p) {if(cnt[p]==0) ans++;cnt[p]++;}
int main(void) {
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&a[i]),b[i]=a[i];
for(int i=1;i<=M;i++) {
scanf("%s",op);
if(op[0]=='R')
scanf("%d%d",&pos[i],&now[i]),prev[i]=b[pos[i]],b[pos[i]]=now[i];
else s++,scanf("%d%d",&x[s].l,&x[s].r),x[s].k=s,x[s].t=i;
}
size=pow(N,2.0/3),std::sort(x+1,x+s+1,cmp);
for(int i=1;i<=s;i++) {
while(L<x[i].l) del(a[L++]);while(L>x[i].l) add(a[--L]);
while(R>x[i].r) del(a[R--]);while(R<x[i].r) add(a[++R]);
while(t<x[i].t) {
t++;if(L<=pos[t]&&pos[t]<=R) del(prev[t]),add(now[t]);
if(pos[t]) a[pos[t]]=now[t];
}
while(t>x[i].t) {
if(L<=pos[t]&&pos[t]<=R) del(now[t]),add(prev[t]);
if(pos[t]) a[pos[t]]=prev[t];t--;
}
as[x[i].k]=ans;
}
for(int i=1;i<=s;i++) printf("%d\n",as[i]);
}
```
by lgvc @ 2022-03-20 09:10:36
我记得这题本来就比较卡常 建议加优化
by Neutralized @ 2022-03-20 09:23:03
```cpp
flp (i, 1, qaqcnt)
{
bel[i] = i / len;
}
```
改成
```cpp
flp (i, 1, n)
{
bel[i] = i / len;
}
```
不开 O2 都能过。
by houzhiyuan @ 2022-03-20 10:09:06
@[BootsH](/user/317805)
by houzhiyuan @ 2022-03-20 10:09:47
@[houzhiyuan](/user/98490) 谢谢。
好的那么我是上下。
by BootsH @ 2022-03-20 10:13:33
谢谢 @[houzhiyuan](/user/98490) @[lgvc](/user/366807) @[Neutralized](/user/538609)
by BootsH @ 2022-03-20 10:14:09