segment tree
tfff1 — 6 years, 8 months ago


#include <bits/stdc++.h>
using namespace std;
#define F(i,s,n) for(int i=s;i<n;i++)
#define PB push_back
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
struct Node {
int left_index, right_index, value;
Node *left_node, *right_node;
};
Node root;
int values[100005];
int query(int left_query, int right_query, Node &node = root) {
if (left_query <= node.left_index && node.right_index <= right_query) {
return node.value;
}
if (right_query <= node.left_index || node.right_index <= left_query) {
return INT_MAX;
}
return min(query(left_query, right_query, *node.left_node), query(left_query, right_query, *node.right_node));
}
void update(int index, int new_value, Node &node = root) {
if (index < node.left_index || node.right_index <= index) {
return;
}
if (node.right_index - node.left_index == 1) {
node.value = new_value;
return;
}
update(index, new_value, *node.left_node);
update(index, new_value, *node.right_node);
node.value = min(node.left_node->value, node.right_node->value);
}
void build(Node &node = root) {
if (node.right_index - node.left_index == 1) {
node.value = values[node.left_index];
return;
}
node.left_node = new Node();
node.right_node = new Node();
Node &left_node = *node.left_node;
Node &right_node = *node.right_node;
left_node.left_index = node.left_index;
left_node.right_index = (node.left_index + node.right_index) / 2;
right_node.left_index = left_node.right_index;
right_node.right_index = node.right_index;
build(left_node);
build(right_node);
node.value = min(left_node.value, right_node.value);
}
void create(int size) {
root.left_index = 0;
root.right_index = size;
build();
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &values[i]);
}
create(n);
for (int i = 0; i < m; i++){
char query_type;
scanf("\n%c", &query_type);
if (query_type == 'M') {
int index, value;
scanf("%d %d", &index, &value);
update(index, value);
} else if (query_type == 'Q') {
int left_index, right_index;
scanf("%d %d", &left_index, &right_index);
printf("%d\n", query(left_index, right_index + 1));
}
}
}