Given an array of n integers and q operations, the task is to handle two types of requests efficiently:

1. Update: Set the value at index x to d.
2. Query: For a range [l, r], find the minimum value and count how many times it appears in that range.

Data Structure Design

We define a structure AggData to store the minimum value and its frequency within a segment. The combination logic for merging two segments is defined as follows:

• If the left minimum is smaller, take the left data.
• If the right minimum is smaller, take the right data.
• If equal, keep the minimum value and sum the counts.

struct AggData {
    int smallest;
    int freq;

    AggData() : smallest(INT_MAX), freq(0) {}
    AggData(int v, int c) : smallest(v), freq(c) {}
};

AggData merge(AggData left, AggData right) {
    if (left.smallest < right.smallest) return left;
    if (right.smallest < left.smallest) return right;
    return AggData(left.smallest, left.freq + right.freq);
}

Segment Tree Implementation

The tree is stored in an array tree of size 4 * n. We use index 1 as the root.

Building the Tree: Initialize leaf nodes with the array values (frequency 1) and internal nodes by merging childern.

AggData tree[4 * N];
int arr[N];

void build_tree(int node, int start, int end) {
    if (start == end) {
        tree[node] = AggData(arr[start], 1);
        return;
    }
    int mid = (start + end) / 2;
    build_tree(node * 2, start, mid);
    build_tree(node * 2 + 1, mid + 1, end);
    tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

Point Update: Recursively traverse to the leaf, update the value, and recalculate ancestors.

void update_point(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = AggData(val, 1);
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update_point(node * 2, start, mid, idx, val);
    else update_point(node * 2 + 1, mid + 1, end, idx, val);
    tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

Range Query: Return the aggregated data for the interval [l, r].

AggData query_range(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return AggData(INT_MAX, 0);
    if (l <= start && end <= r) return tree[node];

    int mid = (start + end) / 2;
    AggData left_res = query_range(node * 2, start, mid, l, r);
    AggData right_res = query_range(node * 2 + 1, mid + 1, end, l, r);
    return merge(left_res, right_res);
}

Main Execution Logic

Read input, build the structure, and process operations.

int main() {
    int n, q;
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++) std::cin >> arr[i];
    
    build_tree(1, 1, n);

    while (q--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int x, d;
            std::cin >> x >> d;
            update_point(1, 1, n, x, d);
        } else {
            int l, r;
            std::cin >> l >> r;
            AggData res = query_range(1, 1, n, l, r);
            std::cout << res.smallest << " " << res.freq << "\n";
        }
    }
    return 0;
}