QMunte_CAC

#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 100000 + 5;

int N;
int v[NMAX];

struct Node {
    int st, dr;
    int cnt;
    vector <int> stk;
} tree[4 * NMAX];

void unite(Node &res, const Node a, const Node &b) {
    if (res.dr == -1) {
        res = b;
        return ;
    }

    res.cnt = a.cnt + b.cnt;
    res.stk = a.stk;
    for (auto it: b.stk) {
        while (res.stk.size() > 1 && res.stk[res.stk.size() - 2] < res.stk[res.stk.size() - 1] && res.stk[res.stk.size() - 1] > it)
            res.cnt ++, res.stk.pop_back();
        res.stk.push_back(it);
    }
}

void build(int node, int st, int dr) {
    tree[node].st = st, tree[node].dr = dr;

    if (tree[node].st == tree[node].dr) {
        tree[node].stk.push_back(v[st]);
        return ;
    }

    int mid = (st + dr) >> 1;
    build(node << 1, st, mid);
    build((node << 1) + 1, mid + 1, dr);

    unite(tree[node], tree[node << 1], tree[(node << 1) + 1]);
}

Node res;
void query(int node, int st, int dr) {
    if (tree[node].st == st && tree[node].dr == dr) {
        unite(res, res, tree[node]);
        return ;
    }

    int mid = (tree[node].st + tree[node].dr) >> 1;
    if (dr <= mid)
        query(node << 1, st, dr);
    else if (st > mid)
        query((node << 1) + 1, st, dr);
    else {
        query(node << 1, st, mid);
        query((node << 1) + 1, mid + 1, dr);
    }
}

void update(int node, int where, int val) {
    if (tree[node].st == tree[node].dr) {
        tree[node].stk = {val};
        v[where] = val;
        return ;
    }

    int mid = (tree[node].st + tree[node].dr) >> 1;
    if (where <= mid)
        update(node << 1, where, val);
    else
        update((node << 1) + 1, where, val);
    unite(tree[node], tree[node << 1], tree[(node << 1) + 1]);
}

int main()
{
    ifstream cin("qmunte.in");
    ofstream cout("qmunte.out");

    int M = 0;
    cin >> N >> M;

    for (int i = 1; i <= N; ++ i)
        cin >> v[i];
    build(1, 1, N);
    cerr << "DONE BUILD" << endl;

    for (int i = 1; i <= M; ++ i) {
        int type, a, b;
        cin >> type >> a >> b;

        if (type == 1)
            update(1, a, b);
        else {
            res.dr = -1;
            query(1, a, b);
            cout << res.cnt << '\n';
        }

        if (i % 10000 == 0)
            cerr << "DONE " << i << endl;
    }
    return 0;
}