这个其实就是RMQ (Range Minimum/Maximum Query),求区间极值问题.

解决这道题有三个方法:

1.朴素算法

2.线段树

3.ST算法(即dp)

第一种显然不可行,我用的是第三种:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 41ms

├ 测试数据 06：答案正确... 166ms

├ 测试数据 07：答案正确... 212ms

├ 测试数据 08：答案正确... 291ms

├ 测试数据 09：答案正确... 462ms

├ 测试数据 10：答案正确... 447ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1619ms

好像有点慢了.

大体算法:

f表示从第i个数起连续2^j个数中的最大值,f:=max(f,f).

预处理所有f.

所以这是离线算法.预处理时间为O(n log n);

询问时只需O(1),因为任何一个数都可以分成两个2的幂次方之和:

k:=trunc(ln(r-l+1)/ln(2));

ans:=max(f[l,k],f[r-2^k+1,k]).

细节注意:

1.数组范围;

2.先循环j值再循环i值;

3.数据类型要用int64;

4.2^N=trunc(exp(ln(2)*n)).

线段树 81行

90分.求第四个点数据

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...程序输出比正确答案短

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 56ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 103ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 197ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

60行程序 秒杀！！！！！！！！！！！！！

是第一个吗？

利用线段树的思想，用点来表示一个区间的最大值

类似于2维数组，建树之后，

find(x,y)在区域里搜索一下就 o 了。

PS： XiaoX大牛 指导....

RMQ - -

囧，第一次写……

果然好用

很牛B的方法，可惜只过了一个————————————南无阿弥陀佛！善哉善哉

program Project1;

var

i,j,m,n:longint;

best,a,b,ss:array[1..10000000] of longint;

begin

readln(n);

for i:=1 to n do read(ss[i]);

readln(m);

for i:=1 to m do best[i]:=0;

for i:=1 to m do readln(a[i],b[i]);

for i:=1 to m do

for j:=a[i] to b[i] do if ss[j]>best[i] then best[i]:=ss[j];

for i:=1 to m do writeln(best[i]);

end.

还是C++爽,33行Code搞定

'

p.s.

用cin:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 306ms

├ 测试数据 06：答案正确... 603ms

├ 测试数据 07：答案正确... 744ms

├ 测试数据 08：答案正确... 853ms

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：2578ms

用scanf:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：90ms

以原数组为叶子结点，自底向上构建完全二叉树……浪费 好多空间……

每个结点的值 即 它 下方 的 所有 叶子结点中 最大的……

然后 竟然 在只过了样例的情况下 AC了 ，RP……

不过 时间 囧……

├ 测试数据 05：答案正确... 40ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 165ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：592ms

再 交 没用链表的， 同样 的算法 竟然 秒杀了……

85行线段树直接AC了 不过没有0ms

线段树左右边界定为[l,(l+r) div 2]和[(l+r) div 2,r]果然处理还要烦一点,时间效率也下降了

果然这种题目还是RMQ好啊

program xr_11;

type

shu=record

l,r,z,c:longint;

o:int64;

end;

var

a:array[1..2000000]of shu;

b:array[1..200000]of int64;

n,m,i,x,y,o,p:longint;

procedure zao(m,x,y:longint);

begin

a[m].l:=x;

a[m].r:=y;

a[m].z:=(x+y)div 2;

if y-x>=1 then

begin

zao(m*2,x,a[m].z);

zao(m*2+1,a[m].z+1,y);

if a[m*2+1].o>a[m*2].o then a[m].o:=a[m*2+1].o

else a[m].o:=a[m*2].o;

end

else a[m].o:=b[x];

end;

function find(m,x,y:longint):longint;

begin

if(a[m].l=x)and(a[m].r=y) then exit(a[m].o);

if ya[m].z then exit(find(m*2+1,x,y))

else

begin

o:=find(m*2,x,a[m].z);

p:=find(m*2+1,a[m].z+1,y);

if o>p then exit(o) else exit(p);

end;

end;

begin

readln(n);

for i:=1 to n do read(b[i]);

zao(1,1,n);

readln(m);

for i:=1 to m do

begin

readln(x,y);

writeln(find(1,x,y));

end;

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

强烈鄙视掉 要用write(....,' ');

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

haha

用write

1楼太强了！！！！

只要RMQ，24行。

program zrj;

type

shu=record

l,r,z,c:longint;

o:int64;

end;

var

a:array[1..2000000]of shu;

b:array[1..200000]of int64;

n,m,i,x,y,o,p:longint;

procedure zao(m,x,y:longint);

begin

a[m].l:=x;

a[m].r:=y;

a[m].z:=(x+y)div 2;

if y-x>=1 then

begin

zao(m*2,x,a[m].z);

zao(m*2+1,a[m].z+1,y);

if a[m*2+1].o>a[m*2].o then a[m].o:=a[m*2+1].o

else a[m].o:=a[m*2].o;

end

else a[m].o:=b[x];

end;

function find(m,x,y:longint):longint;

begin

if(a[m].l=x)and(a[m].r=y) then exit(a[m].o);

if ya[m].z then exit(find(m*2+1,x,y))

else

begin

o:=find(m*2,x,a[m].z);

p:=find(m*2+1,a[m].z+1,y);

if o>p then exit(o) else exit(p);

end;

end;

begin

readln(n);

for i:=1 to n do read(b[i]);

zao(1,1,n);

readln(m);

for i:=1 to m do

begin

readln(x,y);

writeln(find(1,x,y));

end;

end.

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...程序输出比正确答案短

├ 测试数据 10：答案错误...程序输出比正确答案短

为什么错啊?不是线段树吗?

dolphin死了都过不了，换成puppy 103ms就过了，BS dolphin

算法确实经典，再说一下不要换行，不要用流

这个时刻真的很强大

基本所有A的人都在这里了

裸RMQ 要write而不是writeln

RMQ。。。。。。。。。

curimit牛。。我没猜错的话这个是您1486的AC程序

膜拜一楼..那个是AC代码么..