HDu-5443-The Water Problem-裸のRMQ線分ツリー
1901 ワード
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define inf 0x7fffffff
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 1005;
int st_max[maxn<<2];
int aa[maxn];
inline int maxx(int a,int b) { return a>b?a:b; }
void PushUP(int rt)
{
st_max[rt] = maxx(st_max[rt<<1],st_max[rt<<1|1]);
}
int ok=0;
void build(int l,int r,int rt) {
if (l == r)
{ st_max[rt]=aa[++ok];
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUP(rt);
}
/*
void update(int l,int r,int rt,int st_max[],int op,int num,int val)
{
if (l == r&& l==num)
{
st_max[rt] =val;
return ;
}
int m = (l + r) >> 1;
if (num<=m)
update(lson,st_max,op,num,val);
else
update(rson,st_max,op,num,val);
PushUP(rt,l,r,m, st_max,op);
}
*/
int query_max(int qL,int qR,int l,int r,int rt) //L,R ,lr
{
if (qL <= l && r <= qR) {
return st_max[rt];
}
int m = (l + r) >> 1;
int ret1 = -inf,ret2 = -inf;
if (qL <= m) ret1 = query_max(qL , qR , lson);
if (qR > m) ret2 = query_max(qL , qR , rson);
return maxx(ret1,ret2);
}
int main()
{
int n,m,i,a,b;
int t;
scanf("%d",&t);
while(t--)
{
ok=0;
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&aa[i]);
build(1 , n , 1);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
printf("%d
",query_max(a,b,1,n,1));
}
}
return 0;
}