数组要开大，不要吝啬！

250000，70分

300000，80分

1000000,100分！

VJ不支持%lld 仅支持%I64d

不管你用long long 还是__int64

血的教训 。。。又是一小时浪费 。。。

另外 用%i输出。。也可以 。。。。

水题啊，哈哈

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

LineTree万岁！

终于会线段树了。。。。。

这道题又卡cin....郁闷。。。。。

#include

using namespace std;

int64 n,m,a,b,p[1000001],tree[10000002],st[1000002],en[1000002];

__int64 max(__int64 a,int64 b){return a>b?a:b;}

__int64 maketree(__int64 k,__int64 s,__int64 e)

{

st[k] = s; en[k] = e;

if(s == e) tree[k] = p;

else tree[k] = max(maketree(k*2,s,(s+e)/2),maketree(k*2+1,(s+e)/2+1,e));

return tree[k];

}

__int64 find(__int64 k,__int64 x,__int64 y)

{

if(st[k]==x&&en[k]==y)return tree[k];

int64 t=(st[k]+en[k])>>1;

if(y=t+1) return find(2*k+1,x,y);

return max(find(2*k,x,t),find(2*k+1,t+1,y));

}

int main()

{

scanf("%d", &n);

for(int64 i = 0;i < n;++i) scanf("%I64d", &p[i]);

maketree(1,0,n-1);

scanf("%d", &m);

for(__int64 i = 0;i < m;++i) {scanf("%d %d", &a, &b); printf("%I64d\n",find(1,--a,--b));}

}

有个极小的错误,,,10 times...

50lines线段树轻松搞定

囧.........rz

沙茶题留名……

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

qsort+搜索

轻松AC

http://user.qzone.qq.com/785808346/blog/1247295380

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

嘻嘻，一次就秒杀了 。。。。

线段树 哦 ！

还只用了 70 行

program LLL;

type

arr=record

l,r,lc,rc,max:longint;

end;

var

i,n,m,j,k,maxx,top:longint;

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

a:array[0..1000000]of arr;

function max(j,k:longint):longint;

begin

if j>k then max:=j

else max:=k;

end;

procedure mt(l,r:longint);

var

j,mid:longint;

begin

inc(top);

j:=top;

a[top].l:=l; a[top].r:=r;

a[top].max:=-maxlongint;

if r=l)and(a[k].r

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

orz..........建树时候没有考虑负数，交了9次才AC。。。。。RP太差了

直接朴素线段树

读数的话

如果用 __int64 scanf("%i64d", &n);

如果用 long long scanf("%lld", &n);

需要C++代码的：(应该说写的还是比较清爽的，在神牛面前卖弄一下，别见笑)

http://hi.baidu.com/huyuanming11/blog/item/15ec4408fe0a74c63ac76377.html

数组用long(longint)就可以了

1.注意数组开大点。

2.注意有负数，记得max设为-maxlongint。

3.用线段树的记得程序名(或过程名)一定不能设为linetree。

（为什么？自己试试就知道了）

囧rz......

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

线段树的伟大!!!!!!!!!!!!!!!!!!!!!!!!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

比ST效率高

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

st

为什么Dp时要用2^k呢？