RMQ bst and qsplit

暖身
練習bst和分塊
http://hihocoder.com/contest/hiho18/problem/1

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 1000000
using namespace std;
typedef long long int int64;
int an[10000];
int trunk[100];
int main()
{
int n;scanf("%d", &n);
for(int lx = 0;lx < n;lx++)
scanf("%d", an+lx);
int Q = (int)sqrt(n);
for(int lx = 0;lx < n/Q;lx++)
trunk[lx] = INF;
for(int lx = 0;lx < n;lx++)
trunk[lx/Q] = min(trunk[lx/Q], an[lx]);
int k; scanf("%d", &k);
while(k--){
int op, a, b;scanf("%d %d %d", &op, &a, &b);
if(op == 0){
a--, b--;
int qa = a/Q, qb = b/Q;
int gmin = INF;
if(qa == qb or qa == qb-1){
for(int lx = a;lx <= b;lx++)
gmin = min(gmin, an[lx]);
}else{
for(int lx = a;lx < a+Q;lx++)
gmin = min(gmin, an[lx]);
for(int lx = b;lx > b-Q;lx--)
gmin = min(gmin, an[lx]);
for(int lx = qa+1;lx <= qb-1;lx++)
gmin = min(gmin, trunk[lx]);
}
printf("%d\n", gmin);
}else{
a--;
int qa = a/Q;
an[a] = b;
trunk[a/Q] = INF;
for(int lx = qa*Q;lx < (qa+1)*Q;lx++)
trunk[a/Q] = min(trunk[a/Q], an[lx]);
}
}
return 0;
}

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<vector>

#include<utility>

#include<map>

#include<set>

#include<queue>

#include<cmath>

#define INF 100000000

using namespace std;

typedef long long int int64;

int tree[200000];

int base;

void init(int n){

base = (1<<(int(ceil(log2(n+10))))) - 1;

for(int lx = 1;lx <= 2*base+1;lx++)

tree[lx] = INF;

return;

}

int query(int a, int b){

int gmin = INF;

for(a += base-1, b+= base+1; a^b^1;a>>=1, b>>=1){

if(~a&1) gmin = min(tree[a^1], gmin);

if(b&1) gmin = min(tree[b^1], gmin);

}

return gmin;

}

void modify(int p, int x){

p += base; tree[p] = x;

for(p>>=1;p;p>>=1){

tree[p] = min(tree[2*p], tree[2*p+1]);

}

return;

}

int main()

{

int n;scanf("%d", &n);

init(n);

for(int lx = 1;lx <= n;lx++){

int inp;scanf("%d", &inp);

modify(lx, inp);

}

int k; scanf("%d", &k);

while(k--){

int o, a, b;scanf("%d %d %d", &o, &a, &b);

if(o == 0)

printf("%d\n", query(a, b));

else

modify(a, b);

}

return 0;

}