max_count_segment_tree.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = (int)3e5 + 10;
int a[N];
const int INF = (int)1e18;

class Node{
    public:
    int mx;
    int cnt;
    Node(){
        mx = 0;
        cnt = 0;
    }
    Node(int mx, int cnt){
        this->mx = mx;
        this->cnt = cnt;
    }
};

class MaxCST{
    Node t[4 * N];
    public :
    void build(int node, int l, int r){
        if(l == r){
            t[node].mx = a[l];
            t[node].cnt = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
        merge(node);
    }
    void update(int node, int l, int r, int i, int val){
        if(l > i || r < i)  return;
        if(l == r){
            t[node] = Node(val, 1);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, i, val);
        update(2 * node + 1, mid + 1, r, i, val);
        merge(node);
    }
    Node rmax(int node, int l1, int r1, int l, int r){
        if(l1 > r || r1 < l)    return Node(-INF, 0);
        if(l1 >= l && r1 <= r)  return t[node];
        int mid = (l1 + r1) / 2;
        Node left = rmax(2 * node, l1, mid, l, r);
        Node right = rmax(2 * node + 1, mid + 1, r1, l, r);
        return calculate(left, right);
    }
    private:
    void merge(int node){
        t[node] = calculate(t[2 * node], t[2 * node + 1]);
    }
    Node calculate(Node left_node, Node right_node){
        if(left_node.mx > right_node.mx)    return left_node;
        else if(right_node.mx > left_node.mx)   return right_node;
        else return Node(left_node.mx, left_node.cnt + right_node.cnt);
    }
};


int32_t main(){
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    MaxCST seggs;
    seggs.build(1, 1, n);
    while(q--){
        int type; cin >> type;
        if(type == 1){
            int i, val; cin >> i >> val; i++;
            seggs.update(1, 1, n, i, val);
        }else{
            int l, r; cin >> l >> r; l++;
            Node ans = seggs.rmax(1, 1, n, l, r);
            cout << ans.mx << ' ' << ans.cnt << '\n';
        }
    }
}