- 天才的记忆
- 2016-10-13 23:31:19 @
#include<bits/stdc++.h>
#include<algorithm>
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define m(x) tree[x].m
using namespace std;
struct xianduanshu
{
int lson;
int rson;
int m;
}tree[201000 << 2];
int num[201000];
void buildtree(int i,int l,int r)
{
ls(i)=l;
rs(i)=r;
if (l==r) m(i)=num[l];
if (l==r) return;
int mid((l + r) >> 1);
buildtree(i << 1, l, mid);
buildtree(i << 1 | 1, mid + 1, r);
m(i)=max(m(i<<1),m(i<<1|1));
}
int query(int i,int ql,int qr)
{
if (ql<=ls(i)&&rs(i)<=qr)
return m(i);
if (qr<ls(i)||ql>rs(i)) return 0;
return max(query(i<<1,ql,qr),query(i<<1|1,ql,qr));
}
int main()
{
int n;
scanf("%d",&n);
memset(num,0,sizeof(num));
memset(tree,0,sizeof(tree));
for (int i=1;i<=n;i++) scanf("%d",&num[i]);
buildtree(1,1,n);
int m;
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(1,l,r));
}
}
2 条评论
-
lrj124 LV 10 @ 2016-10-16 08:02:29
初始值要设1000000000
-
2016-10-13 23:32:03@
闭眼线段树,为什么是错的!!!!!!!!!!!!!!!!!!!!!!!!!!错两个点
- 1