/*RMQ 更新最小值操作 By:draymonder*/
#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1 << 17;
const int INF = 0x3f3f3f3f;
typedef long long LL;
int n,s[2*maxn-1];
void init(int a)//把元素个数扩充到2的幂 简便
{
n = 1;
while (n < a)
n*=2;
for(int i=0;i<2*n-1;i++)
s[i] = INF; //把所有的值 都变成INF
}
void update(int k,int a)//把第k个值更新为a
{
k += n-1;
s[k] = a;//找到 只是k的这个区间的位置 然后依次更新
while (k > 0)
{
k = ( k - 1 )/2;
s[k] = min(s[k*2+1],s[k*2+2]);
}
}
//求[a,b)的最小值
//后面的参数是为了计算起来方便而传入的
//k是节点的编号,l,r表示这个节点对应的[l,r)区间
//在外部调用的时候用query(a,b,0,0,n)
int query(int a,int b,int k,int l,int r)
{
if(r <= a || b <= l) return INF;//[a,b) 与 [l,r)不相交
//如果 [a,b)完全包含[l,r) 直接返回当前k节点的值
if(a <= l && r<= b) return s[k];
else {
//否则返回两个儿子中值较小者
int v1 = query(a,b,k*2+1, l , (l+r)/2);
int v2 = query(a,b,k*2+1,(l+r)/2 , r);
return min(v1,v2);
}
}