F - Second Largest Query (atcoder.jp)
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <numeric>
#include <functional>
#include <climits>
//#include <windows.h>
using namespace std;
#define ll long long
#define db double
#define PII pair<int, int>
#define TUP tuple<int, int, int>
const int inf = 0x3f3f3f3f;
ll mod = 1e15 + 17;
ll q_pow(ll a, ll b) { ll ret = 1; while (b) { if (b & 1)ret = ret * a % mod; b >>= 1; a = a * a % mod; }return ret; }
ll gcd(ll a, ll b) { if (!b)return a; return gcd(b, a % b); }
const int N = 1e6;
struct Node {
int max0, cnt0, max1, cnt1;
}tree[N];
Node add(Node p, Node q) {
if (p.max0 == q.max0) {
if (p.max1 == q.max1) return (Node){p.max0, p.cnt0 + q.cnt0, p.max1, p.cnt1 + q.cnt1};
return (Node){p.max0, p.cnt0 + q.cnt0, max(p.max1, q.max1), p.max1 > q.max1 ? p.cnt1 : q.cnt1};
}
if (p.max0 < q.max0) swap(p, q);
if (p.max1 == q.max0) return (Node){p.max0, p.cnt0, p.max1, p.cnt1 + q.cnt0};
return (Node){p.max0, p.cnt0, max(p.max1, q.max0), p.max1 > q.max0 ? p.cnt1 : q.cnt0};
}
void update(int l, int r, int node, int ind, int num) {
if (l == r) {
tree[node].max0 = num;
return;
}
int mid = (l + r) >> 1;
if (ind <= mid) update(l, mid, node * 2 + 1, ind, num);
else update(mid + 1, r, node * 2 + 2, ind, num);
tree[node] = add(tree[node * 2 + 1], tree[node * 2 + 2]);
return;
}
Node query(int l, int r, int node, int L, int R) {
if (L <= l and r <= R) return tree[node];
int mid = (l + r) >> 1;
if (mid >= R) return query(l, mid, node * 2 + 1, L, R);
if (mid < L) return query(mid + 1, r, node * 2 + 2, L, R);
return add(query(l, mid, node * 2 + 1, L, R), query(mid + 1, r, node * 2 + 2, L, R));
}
void build_tree(int l, int r, int node) {
if (l == r) {
cin >> tree[node].max0;
tree[node].cnt0 = 1;
return;
}
int mid = (l + r) >> 1;
build_tree(l, mid, node * 2 + 1);
build_tree(mid + 1, r, node * 2 + 2);
tree[node] = add(tree[node * 2 + 1], tree[node * 2 + 2]);
return;
}
void yelp_solve() {
int n, q, op, x, y;
cin >> n >> q;
build_tree(0, n - 1, 0);
while (q--) {
cin >> op >> x >> y;
if (op == 1) update(0, n - 1, 0, --x, y);
else cout << query(0, n - 1, 0, --x, --y).cnt1 << endl;
}
return;
}
int main() {
int r = 1;
//cin >> r;
while (r--) yelp_solve();
return 0;
}