昨晚 ABC F 求调，样例二没过

/*
    Author: Rainypaster(lhy)
    Time: 03/03/2024
    File: [ABC] C:\Rainypaster\ABC\ABC343F.cpp
    Email: 2795974905@qq.com
*/
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
    template<typename T>
    T read(T x)
    {
        T sum = 0, opt = 1;
        char ch = getchar();
        while(!isdigit(ch)) opt = (ch == '-') ? -1 : 1, ch = getchar();
        while( isdigit(ch)) sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
        return sum * opt;
    }

}
#define read IO::read(0)
#define rep(i, n) for(int i = 1; i <= n; i ++)
#define repa(i, n) for(int i = 0; i < n; i ++)
#define repb(i, n) for(int i = 1; i <= n; i ++)
#define repc(i, n) for(int i = 0; i < n; i ++)
#define lson (u << 1)
#define rson (u << 1 | 1)
#define gcd(a, b) __gcd(a, b)

const int N = 1e5 + 5;

struct node
{
    int l, r;
    int max, max_cnt, mex, mex_cnt;
}tr[N << 2];

int a[N];

struct Segment_Tree
{
    node push_up(node pl, node pr)
    {  
        node res = {0, 0, 0, 0, 0, 0};
        res.l = pl.l, res.r = pr.r;
        if(pl.max == pr.max)
        {
            res.max = pl.max;
            res.max_cnt = pl.max_cnt + pr.max_cnt;
            if(pl.mex == pr.mex){
                res.mex = pl.mex;
                res.mex_cnt = pl.mex_cnt + pr.mex_cnt;
            }
            else if(pl.mex < pr.mex)
            {
                res.mex = pr.mex;
                res.mex_cnt = pr.mex_cnt;
            }
            else{
                res.mex = pl.mex;
                res.mex_cnt = pl.mex_cnt;
            }
        }
        else if(pl.max < pr.max)
        {
            res.max = pr.max;
            res.max_cnt = pr.max_cnt;
            if(pl.max == pr.mex){
                res.mex = pl.max;
                res.mex_cnt = pl.max_cnt + pr.mex_cnt;
            }
            else if(pl.max > pr.mex)
            {
                res.mex = pl.max;
                res.mex_cnt = pl.max_cnt;
            }
            else {
                res.mex = pr.mex;
                res.mex_cnt = pr.mex_cnt;
            }
        }
        else{ 
            res.max = pl.max;
            res.max_cnt = pl.max_cnt;
            if(pl.mex == pr.max)
            {
                res.mex = pl.mex;
                res.mex_cnt = pl.mex_cnt + pr.max_cnt;
            }
            else if(pl.mex > pr.max)
            {
                res.mex = pl.mex;
                res.mex_cnt = pl.mex_cnt;
            }
            else{
                res.mex = pr.max;
                res.mex_cnt = pr.max_cnt;
            }
        }
        return res;
    }
    void build(int u, int l, int r)
    {
        tr[u].l = l, tr[u].r = r;
        if(l == r)
        {
            tr[u].max = a[l];
            tr[u].max_cnt = 1;
            tr[u].mex = 0;
            tr[u].mex_cnt = 0;
            return ;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid), build(rson, mid + 1, r);
        tr[u] = push_up(tr[lson], tr[rson]);
    }
    void update(int u, int l, int x){
        if(tr[u].l == l && tr[u].r == l){
            tr[u].max = x;
            tr[u].max_cnt = 1;
            return ;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) update(lson, l, x);
        else update(rson, l, x);
        tr[u] = push_up(tr[lson], tr[rson]);
    }

    node query(int u, int l, int r)
    {
        if(l <= tr[u].l && tr[u].r <=  r) return tr[u];
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) return query(lson, l, r);
        else if(r > mid) return query(rson, l, r);
        else return push_up(query(lson, l, r), query(rson, l, r));
    }
}seg;

void solve()
{  
    int n = read, m = read;

    rep(i, n) a[i] = read;

    seg.build(1, 1, n);

    while(m -- )
    {
        int op = read;
        if(op == 1) {
            int x = read, y = read;
            seg.update(1, x, y);
        }   
        else {
            int x = read, y = read;
            cout << seg.query(1, x, y).mex_cnt << endl;
        }
    }
    
}

int main()
{
    int T = 1;
    while(T -- ) solve();
    return 0;
}