这题我过得很迥，秒的。

我用的是

快排+直接搜索。。。（无语）；

这题其实就是个RMQ问题，百度一下，你就知道。

方法有3种，百度一下，你又知道。

哇、谁扔的鸡蛋。。。呜呜，臭死了。T_T

回宿舍洗澡去。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

线段树。。也是不能秒杀。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

经典的ST算法，NlogN的复杂度，可惜不能秒杀。。。

第一次提交，竟然看错了数据范围，N

莫名其妙的题目，只是差在一个边读入边处理，一个读入完在处理，前面的AC后面的只有40分！！郁闷，哪个大牛帮忙解释下为什么啊！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

....ms了....

树状数组

为什么我写writeln(find(1,n,1,u,v)) 第五个点出来格式错误? 改成write就过了?

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

人生的第一个线段树

线段树 线段树 线段树~~

搞笑了，这题有问题把……

这是测评结果（刚开始出现的）

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

过一会儿就变成unac，然后一查，发现我这道题过了……什么玩意啊？vj是不是有bug啊？

不信请看此题状态，你会发现我只有60分，但实际点我名字，我是过了的……

郁闷啊……

不过反正是过了……不管他了，只是请各位仁兄看看有没有同样情况……

st算法

很快

program st;

var f:array[0..200000,0..30] of longint;

i,j,k,l,m,n,o,p,q,r:longint;

function max(x,y:longint):longint;

begin if x>y then exit(x);exit(y);end;

begin

readln(n);

for i:=1 to n do read(f);

for j:=1 to trunc(ln(n)/ln(2)) do

for i:=1 to n-1 shl j+1 do

f:=max(f,f[i+1 shl (j-1),j-1]);

readln(q);

for i:=1 to q do

begin

read(l,r);

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

p:=max(f[l,k],f[r-1 shl k+1,k]);

writeln(p);

end;

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

强烈ORZ ST！！！！！！！！

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

第一次线段树，N次的80分！火了，直接开2000000的数组，过了.....

赤裸裸的线段树。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次AC 一鼓作气 真舒服 蛤蛤

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

人生第一次写线段树

写了 75行

虽然wa了 几遍但终于AC 了

额...第一次写线段树。30行AC。数组一定要开到524287以上！

rmq

这题不至于线段树吧......

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

running了20几秒。。。

var

key:array[0..1000000] of longint;

left,right,n,m:longint;

function max(x,y:longint):longint;

begin

if x>y then

max:=x

else

max:=y;

end;

procedure build(node,l,r:longint);

begin

if l=r then

begin

read(key[node]);

exit;

end;

build(node*2,l,(l+r) div 2);

build(node*2+1,(l+r) div 2+1,r);

key[node]:=max(key[node*2],key[node*2+1]);

end;

function ask(node,l,r:longint):longint;

begin

if (left=r) then

exit(key[node]);

ask:=-maxlongint;

if left=(l+r) div 2+1 then

ask:=max(ask,ask(node*2+1,(l+r) div 2+1,r));

end;

begin

readln(n);

build(1,1,n);

readln(m);

repeat

dec(m);

readln(left,right);

writeln(ask(1,1,n));

until m=0;

end.

数组真的要开到1000000，我WA了无数次都是60分就是因为数组开小了！

一看,就一个线段树,

再看,忘了怎么写