HackerEarth/Range Minimum Query.cpp at master · ayushjain02/HackerEarth · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

int st[400000];
int a[100100];

void build(int ind,int start,int end){
	if(start==end)
		st[ind]=a[end];
	else{
		int mid=(start+end)/2;
		build(2*ind+1,start,mid);
		build(2*ind+2,mid+1,end);
		st[ind]=min(st[2*ind+1],st[2*ind+2]);
	}
}

int query(int l,int r,int ind,int start,int end){
	if(l>end || r<start)
		return INT_MAX;
	if(l<=start && r>=end)
		return st[ind];

	int mid=(start+end)/2;
	int left=query(l,r,2*ind+1,start,mid);
	int right=query(l,r,2*ind+2,mid+1,end);
	return min(left,right);
}

void update(int x,int y, int ind, int start, int end){
	if(start==end){
		a[x]=y;
		st[ind]=y;
	}
	else{
		int mid=(start+end)/2;
		if(start<=x && x<=mid )
			update(x,y,2*ind+1,start,mid);
		else
			update(x,y,2*ind+2,mid+1,end);

		st[ind]=min(st[2*ind+1],st[2*ind+2]);
	}
}

int main()
{
	int n,q,x,y,i;
	char typ;
	cin >> n >> q;
	for(i=0;i<n;i++)
		cin >> a[i];
	build(0,0,n-1);
	while(q--)
	{
		cin >> typ >> x >> y;
		if(typ=='q')
			cout << query(x-1,y-1,0,0,n-1) << endl;
		else
			update(x-1,y,0,0,n-1);
	}
	return 0;
}