1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;
#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))
#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
using ll=long long;
using a4=std::array<int,4>;
char opt;
int n,m,tot=1,a[(int)2e5+9],fk,belong[(int)2e5+9],l=1,r,cnt[(int)1e6+9],ans,now=1,res[(int)2e5+9];
struct{
int pos,val;
}modify[(int)2e5+9];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
vector<a4> q;
for(int i=1,x,y;i<=m;++i){
cin>>opt>>x>>y;
if(opt=='Q'){
q.push_back({x,y,tot,i});
}else {
modify[++tot]={x,y};
}
}
fk=ceil(pow(n,2.0/3.0)*pow(tot,1.0/3.0)/pow(m,1.0/3.0));
for(int i=1;i<=n;++i)belong[i]=(i-1)/fk+1;
sort(all(q),[](const a4 &aa,const a4 &bb){
if(belong[aa[0]]!=belong[bb[0]])return belong[aa[0]]<belong[bb[0]];
if(belong[aa[1]]!=belong[bb[1]])return belong[aa[0]]&1?aa[1]<bb[1]:aa[1]>bb[1];
return aa[2]<bb[2];
});
for(auto [aa,bb,cc,dd]:q){
while(l>aa)ans+=(++cnt[a[--l]]==1);
while(r<bb)ans+=(++cnt[a[++r]]==1);
while(l<aa)ans-=(--cnt[a[l++]]==0);
while(r>bb)ans-=(--cnt[a[r--]]==0);
while(now<cc){
now+=1;
if(modify[now].pos>=aa&&modify[now].pos<=bb){ans-=(--cnt[a[modify[now].pos]]==0);ans+=(++cnt[modify[now].val]==1);}
swap(modify[now].val,a[modify[now].pos]);
}
while(now>cc){
if(modify[now].pos>=aa&&modify[now].pos<=bb){ans-=(--cnt[a[modify[now].pos]]==0);ans+=(++cnt[modify[now].val]==1);}
swap(modify[now].val,a[modify[now].pos]);
now-=1;
}
res[dd]=ans;
}
for(int i=1;i<=m;++i)if(res[i])cout<<res[i]<<"\n";
return 0;
}
|