@[Respons_](/user/357163) 好了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int c1 = 1, c2 = 1;
int n, m, a[N],b[N << 1],cnt[N << 1], level[N << 1], c[N], Ans[N];
struct Q{
int l, r, id, pos, rpos, t;
}q[N];
struct xiu{
int i, a, b;
}g[N];
bool cmp(Q a, Q b){
if(a.pos != b.pos) return a.l < b.l;
if(a.rpos != b.rpos) return a.r < b.r;
return a.t < b.t;
}
void add(int x){
level[cnt[x]]--;
++cnt[x];
level[cnt[x]]++;
}
void del(int x){
level[cnt[x]]--;
--cnt[x];
level[cnt[x]]++;
}
int main(){
scanf("%d%d", &n, &m);
int sz = pow(n, 0.6666666);
int sum = n / sz;
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = a[i];
int tot = n;
for(int i = 1; i <= m; ++i){
int opt;
scanf("%d", &opt);
if(opt == 1){
scanf("%d%d", &q[c1].l, &q[c1].r);
q[c1].id = c1, q[c1].t = c2;
q[c1].pos = (q[c1].l - 1) / sz + 1;
q[c1].rpos = (q[c1].r - 1) / sz + 1;
c1++;
}
else{
scanf("%d%d", &g[c2].i, &g[c2].b);
b[++tot] = g[c2].b;
c2++;
}
}
sort(b + 1, b + 1 + tot);
int len = unique(b + 1, b + 1 + tot) - b - 1;
for(int i = 1; i <= n; ++i){
int p = lower_bound(b + 1, b + 1 + len, a[i]) - b;
a[i] = c[i] = p;
}
for(int i = 1; i < c2; ++i){
int p = lower_bound(b + 1, b + 1 + len, g[i].b) - b;
g[i].b = p;
g[i].a = c[g[i].i];
c[g[i].i] = g[i].b;
}
sort(q + 1, q + c1, cmp);
int L = 1, R = 0, T = 1;
for(int i = 1; i < c1; ++i){
while(L > q[i].l) add(a[--L]);
while(R < q[i].r) add(a[++R]);
while(L < q[i].l) del(a[L++]);
while(R > q[i].r) del(a[R--]);
while(T < q[i].t){
if(L <= g[T].i && g[T].i <= R){
add(g[T].b), del(g[T].a);
}
a[g[T].i] = g[T].b;
++T;///////////////////////////////////////////////////////////
}
while(T > q[i].t){
--T;
if(L <= g[T].i && g[T].i <= R){
add(g[T].a), del(g[T].b);
}
a[g[T].i] = g[T].a;
}
for(int j = 1; ; ++j){
if(!level[j]){
Ans[q[i].id] = j;
break;
}
}
}
for(int i = 1; i < c1; ++i){
printf("%d\n", Ans[i]);
}
}
```
by 天南星魔芋 @ 2022-05-17 15:39:20
@[天南星魔芋](/user/399239) 谢谢/bx
by shyr @ 2022-05-18 12:24:51