rt，使用线段树维护答案序列

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int rock[N];
int a[N];
int n,m;
int ask[N][4];
vector <int> lisan;
struct node
{
    int l,r;
    int sum;
    int tag;
}tree[4 * N];
void build(int l,int r,int num)
{
    tree[num].l = l;
    tree[num].r = r;
    if(l == r)
    {
        tree[num].sum = 0;
        return ;
    }
    int mid = (l + r) / 2;
    build(l,mid,2 * num);
    build(mid + 1,r,2 * num + 1);
    tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
    return ;
}

void pushdown(int num)
{
    tree[2 * num].sum += (tree[2 * num].r - tree[2 * num].l + 1) * tree[num].tag;
    tree[2 * num].tag += tree[num].tag;
    tree[2 * num + 1].sum += (tree[2 * num + 1].r - tree[2 * num + 1].l + 1) * tree[num].tag;
    tree[2 * num + 1].tag += tree[num].tag;
    tree[num].tag = 0;
    return ;
}

void pushup(int num)
{
    tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
    return ;
}
void modify(int num,int L,int R,int x)
{
    if(tree[num].r < L || tree[num].l > R) return ;
    if(L <= tree[num].l && R >= tree[num].r)
    {
        tree[num].sum += (tree[num].r - tree[num].l + 1) * x;
        tree[num].tag += x;
        return ;
    }
    if(tree[num].tag != 0) pushdown(num);
    modify(2 * num,L,R,x);
    modify(2 * num + 1,L,R,x);
    pushup(num);
}
int query(int num,int L,int R)
{
    if(tree[num].r < L || R < tree[num].l) return 0;
    if(L <= tree[num].l && R >= tree[num].r) return tree[num].sum;
    if(tree[num].tag != 0) pushdown(num);
    return query(num * 2,L,R) + query(num * 2 + 1,L,R);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int t = 1;t <= n;t++)
    {
        cin >> rock[t];
        lisan.push_back(rock[t]);
    }
    for(int t = 1;t <= m;t++)
    {
        cin >> ask[t][1];
        if(ask[t][1] == 1)
        {
            cin >> ask[t][2];
            lisan.push_back(ask[t][2]);
        }
        else
        {
            cin >> ask[t][2] >> ask[t][3];
            lisan.push_back(ask[t][3]);
        }
    }
    sort(lisan.begin(),lisan.end());    
    lisan.erase(unique(lisan.begin(),lisan.end()),lisan.end());

    for(int t = 1;t <= n;t++)
    {
        rock[t] = (int)(lower_bound(lisan.begin(),lisan.end(),rock[t]) - lisan.begin()) + 1;
        //cout << rock[t] << " ";
    }
    //cout << endl;
    for(int t = 1;t <= m;t++)
    {
        if(ask[t][1] == 1)
        {
            cin >> ask[t][2];
            ask[t][2] = (int)(lower_bound(lisan.begin(),lisan.end(),ask[t][2]) - lisan.begin()) + 1;
            //cout << ask[t][2] << endl;
        }
        else
        {
            cin >> ask[t][2] >> ask[t][3];
            ask[t][3] = (int)(lower_bound(lisan.begin(),lisan.end(),ask[t][3]) - lisan.begin()) + 1;
        }
    }
    build(1,n,1);
    for(int t = 1;t <= n;t++)
    {
        if(rock[t - 1] < rock[t]) modify(1,rock[t - 1] + 1,rock[t],1);
    }
    for(int t = 1;t <= m;t++)
    {
        if(ask[t][1] == 1)
        {
            cout << query(1,ask[t][2],ask[t][2]) << endl;
        }
        else
        {
            int pos = ask[t][2];
            if(rock[pos - 1] < rock[pos]) modify(1,rock[pos - 1] + 1,rock[pos],-1);
            if(rock[pos] < rock[pos + 1]) modify(1,rock[pos] + 1,rock[pos + 1],-1);
            rock[pos] = ask[t][3];
            if(rock[pos - 1] < rock[pos]) modify(1,rock[pos - 1] + 1,rock[pos],1);
            if(rock[pos] < rock[pos + 1]) modify(1,rock[pos] + 1,rock[pos + 1],1);
        }
    }
    return 0;
}