RT,使用分块直接做。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
const int B = 1000;

struct node
{
    int d,pos;
    bool flag;
}a[maxn];

int C[maxn];
int tmp[maxn];
int len,num;
int mx[maxn],mxx[maxn];
int sum[B][maxn];

struct query
{
    int opt,l,r;
}q[maxn];

int n,m;
int block[maxn];

void init()
{
    num = n / len;
    for(int i = 1;i <= num;i++)
    {
        for(int j = (i - 1) * len + 1;j <= min(n,i * len);j++)
        {
            block[j] = i;
        }
    }
    if(num * len < n)
    {
        num++;
        for(int j = (num - 1) * len + 1;j <= n;j++)
        {
            block[j] = num;
        }
    }
    for(int i = 1;i <= n;i++)
    {
        sum[block[i]][a[i].d]++;
        if(a[i].d > mx[block[i]])
        {
            mxx[block[i]] = mx[block[i]];
            mx[block[i]] = a[i].d;
        }
        else if(a[i].d > mxx[block[i]] && mx[block[i]] != a[i].d)
        {
            mxx[block[i]] = a[i].d;
        }
    }
}

int main()
{
    cin >> n >> m;
    len = sqrt(n);
    int cnt = 0;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i].d;
        tmp[++cnt] = a[i].d;
    }
    for(int i = 1;i <= m;i++)
    {
        cin >> q[i].opt >> q[i].l >> q[i].r;
        if(q[i].opt == 1)
        {
            tmp[++cnt] = q[i].r;
            a[++cnt].d = q[i].r;
            a[cnt].flag = 1;
            a[cnt].pos = i;
        }
    }
    sort(tmp + 1,tmp + cnt + 1);
    int cnt1 = unique(tmp + 1,tmp + cnt + 1) - tmp - 1;
    for(int i = 1;i <= cnt;i++)
    {
        a[i].d = lower_bound(tmp + 1,tmp + cnt1 + 1,a[i].d) - tmp;
        if(a[i].flag)
        {
            q[a[i].pos].r = a[i].d;
        }
    }
    init();
    for(int i = 1;i <= m;i++)
    {
        int l = q[i].l,r = q[i].r;
        if(q[i].opt == 1)
        {
            sum[block[l]][a[l].d]--;
            a[l].d = r;
            sum[block[l]][a[l].d]++;
            mxx[block[l]] = mx[block[l]] = -63;
            for(int j = (block[l] - 1) * len + 1;j <= min(n,block[l] * len);j++)
            {
                if(a[j].d > mx[block[j]])
                {
                    mxx[block[j]] = mx[block[j]];
                    mx[block[j]] = a[j].d;
                }
                else if(a[j].d > mxx[block[j]] && mx[block[j]] != a[j].d)
                {
                    mxx[block[j]] = a[j].d;
                }
            }
        }
        else
        {
            int maxx = -63,maxxx = -63;
            if(l == r)cout << 0 << '\n';
            else
            {
                for(int j = block[l] + 1;j <= block[r] - 1;j++)
                {
                    if(mx[j] > maxx)
                    {
                        maxxx = maxx;
                        maxx = mx[j];
                    }
                    else if(mx[j] > maxxx && maxx != mx[j])
                    {
                        maxxx = mx[j];
                    }
                    if(mxx[j] > maxx)
                    {
                        maxxx = maxx;
                        maxx = mxx[j];
                    }
                    else if(mxx[j] > maxxx && maxx != mxx[j])
                    {
                        maxxx = mxx[j];
                    }
                }
                for(int j = l;j <= min(block[l] * len,n);j++)
                {
                    if(a[j].d > maxx)
                    {
                        maxxx = maxx;
                        maxx = a[j].d;
                    }
                    else if(a[j].d > maxxx && a[j].d != maxx)
                    {
                        maxxx = a[j].d;
                    }
                }
                for(int j = (block[r] - 1) * len + 1;j <= r;j++)
                {
                    if(a[j].d > maxx)
                    {
                        maxxx = maxx;
                        maxx = a[j].d;
                    }
                    else if(a[j].d > maxxx && a[j].d != maxx)
                    {
                        maxxx = a[j].d;
                    }
                }
                int ans = 0;
                for(int j = block[l] + 1;j <= block[r] - 1;j++)
                {
                    ans += sum[j][maxxx];
                }
                for(int j = l;j <= min(block[l] * len,n);j++)
                {
                    if(a[j].d == maxxx)
                    {
                        ans++;
                    }
                }
                for(int j = (block[r] - 1) * len + 1;j <= r;j++)
                {
                    if(a[j].d == maxxx)
                    {
                        ans++;
                    }
                }
                cout << ans << '\n';
            }
        }
    }
    return 0;
}//肥肠暴力的分块做法