#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct A
{
A* father; A* left; A* right;
long long num;
long long l,r;
};
A* head=new A;
long long n,m;
A* a[200001];
void buildatree(long long x,long long y,A* p)
{
p->l=x; p->r=y; p->num=0;
if (x==y) {p->left=p->right=NULL; a[x]=p; return;}
p->left=new A; p->right=new A;
p->left->father=p->right->father=p;
buildatree(x,(x+y)/2,p->left); buildatree((x+y)/2+1,y,p->right);
}
long long max(long long x,long long y) {return x>y?x:y;}
long long min(long long x,long long y) {return xy) return 0;
if (x==p->l&&y==p->r) return p->num;
long long mid=(p->l+p->r)/2;
return max(searchmax(x,min(mid,y),p->left),searchmax(max(x,mid+1),y,p->right));
}
int main()
{
ios::sync_with_stdio(false);
head->father=NULL;
cin >>n;
buildatree(1,n,head);
for (long long i=1;i>x;
A* p=a[i];
while (p->numnum=x; if (p->father==NULL) break; p=p->father;}
}
searchmax(2,3,head);
long long m; cin >>m;
for (long long i=1;i>x1 >>x2; if (x1>x2) continue; cout
2 条评论
-
lzh5032 LV 8 @ 2013-10-17 16:07:38
评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 8648 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 8648 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 8652 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 8652 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 8648 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 8648 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 8652 KiB, score = 10
测试数据 #8: Accepted, time = 156 ms, mem = 8652 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 8652 KiB, score = 10
Accepted, time = 699 ms, mem = 8652 KiB, score = 100program P1514;
var w:array[1..200000]of int64;
t:array[1..800000]of int64;
n,m,i,l,r:longint;
function max(a,b:int64):int64;
begin if a>b then max:=a else max:=b; end;
procedure build(root,l,r:longint);
var mid:longint;
begin
if(l=r)then
begin
t[root]:=w[l]; exit;
end;
mid:=(l+r)div 2;
build(root*2,l,mid); build(root*2+1,mid+1,r);
t[root]:=max(t[root*2],t[root*2+1]);
end;
function ask(root,x,y,l,r:longint):int64;
var mid:longint;
begin
if(x=l)and(y=r)then exit(t[root]);
mid:=(l+r)div 2;
if mid>=y then ask:=ask(root*2,x,y,l,mid)
else
if mid<x then ask:=ask(root*2+1,x,y,mid+1,r)
else ask:=max(ask(root*2,x,mid,l,mid),ask(root*2+1,mid+1,y,mid+1,r));
end;
begin
readln(n);
for i:=1to n do
read(w[i]);
build(1,1,n);
readln(m);
while(m>0)do
begin dec(m);
readln(l,r);
writeln(ask(1,l,r,1,n));
end;
end. -
@ 2013-09-30 22:28:14
同学线段树过不了的吧=-=RMQ就可以了
- 1
