本来是WA，修了几个小细节就T了。

感觉添加，删除那几个函数写的好像没啥问题。

#include<bits/stdc++.h>

using namespace std;

int read()
{
	int x = 0;
    char s = getchar();
    int f = 1; x = 0;
    while(s < '0' || s > '9'){if(s == '-') f = -1; s = getchar();}
    while(s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + (s ^ 48); s = getchar();}
    x *= f;
    return x;
}

void print(int x)
{
	if(x > 9)
		print(x / 10);
	putchar(x % 10 + '0');
}

const int N = 2e5 + 10;

struct Q{
    int l, r, t;
    int id;
}q[N]; // 询问

struct change{
    int pos, col;
}c[N]; //更改

int n, m, len, tot = 0;
int dis[N]; // 离散之后的数据
int cnt[N], recnt[N]; // 数码出现次数 和 出现次数的出现次数
int ans[N];
int b[N];
int qcnt = 0, ccnt = 0;

void Discretization()   //离散化
{
    sort(b, b + tot);
    tot = unique(b, b + tot) - b;
    for(int i = 1; i <= n; i++)
    	dis[i] = lower_bound(b, b + tot, dis[i]) - b;
    for(int i = 1; i <= ccnt; i++)
    	c[i].col = lower_bound(b, b + tot, c[i].col) - b;
}

int id(int k){return k / len + 1;}

bool cmp(Q a, Q b)
{
    return id(a.l) ^ id(b.l) ? id(a.l) < id(b.l) : (id(a.l) & 1 ? a.r < b.r : (a.t < b.t ? a.t < b.t : a.r > b.r));
}

void add(int x)
{
    --recnt[cnt[x]++];
    ++recnt[cnt[x]];
}

void del(int x)
{
    --recnt[cnt[x]--];
    ++recnt[cnt[x]];
}

void update(int i, int now)
{
    if(c[now].pos >= q[i].l && c[now].pos <= q[i].r)
        add(c[now].col), del(dis[c[now].pos]);
    swap(c[now].col, dis[c[now].pos]);
}

int main()
{
    n = read();m = read();
    len = pow(n, 0.66666);
    for(int i = 1; i <= n; i++)
        b[tot++] = dis[i] = read();
    for(int i = 1; i <= m; i++)
    {
        char s;
        cin >> s;
        if(s == '1')
        {
            q[++qcnt].l = read();
            q[qcnt].r = read();
            q[qcnt].id = qcnt;
            q[qcnt].t = ccnt;
        }
        else{
            c[++ccnt].pos = read();
            c[ccnt].col = b[tot++] = read();
        }
    }
    Discretization();
    sort(q + 1, q + qcnt + 1, cmp);
    int l = 1, r = 0, t = 0;
    for(int i = 1; i <= qcnt; i++)
    {
        int ql = q[i].l, qr = q[i].r;
        int qt = q[i].t;
        while(l < ql)   del(dis[l++]);
        while(l > ql)   add(dis[--l]);
        while(r > qr)   del(dis[r--]);
        while(r < qr)   add(dis[++r]);
        while(t < qt)   update(i, ++t);
        while(t > qt)   update(i, t--);
        for(ans[q[i].id] = 1; recnt[ans[q[i].id]] > 0; ans[q[i].id]++);
    }
    for(int i = 1; i <= qcnt; i++)
        print(ans[i]), printf("\n");
    //system("pause");
    return 0;
}