维护一棵排序二叉树即可

type

btree=^node;

node=record

lc,rc:btree; //左、右孩子

d:longint; //当前节点的值

ln,rn:longint; //左节点总数、右子树点总数

ls,rs:longint; //左、右子树和

end;

O(n ^ 2 logn)

预处理就可以直接求出所有(Li,Ri)需要的时间。

编译通过...

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

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

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

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

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

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

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

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

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

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

郁闷，交错程序了。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

同样的代码，超时2次，第三次AC！

PS:两次超时还不是同一组数据！

第31个通过....

Flag 　　Accepted

题号 　　P1459

通过 　　30人

第30个通过的人...

用qword.然后用大小根堆维护中位数,用(小根堆总和-小根堆元素数*中位数)+(大根堆元素数*中位数-大根堆总和)求出这个区间内的值...

然后就可以AC了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

又一道平衡树……

如果用平衡树求中间数的话，总共的预处理时间不是O(n ^ 2 logn)吗？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

treep乱搞，treap常数太大了，好慢

平方的预处理，O（1）的输出就好了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

比赛时快排写错了~郁闷~

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

线段树+离散

为什么同样的程序比赛时候测就是0分。。。。

此题难道不是把每一步的最小值都输出来？我昨天眼花了？为什么昨天明明看到的是一排数字？为什么都是这种垃圾错误，上次也是，气死我了！！！

做法1：区间排序，然后平衡树

做法2：STD

做法3：问TN

做法4：K-th number

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

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

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

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

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

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

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

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

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

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

treap的时间。。

回答一下楼下怎么预处理的问题：

f表示1~j的每个数与a[i]的绝对值差的和。

s=中位数的地方

ans=f-f

用堆更稳一些

编译通过...

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

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

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

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

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

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

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

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

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

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

原来做第一个AC者是如此爽的，

虽然不能秒

不用堆，用BST（连ROTATE都省了，竟然没退化~~）

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

先预处理出每个区间的答案，读入后直接输出。这时，需要维护一个大根堆和一个小根堆，其

中小根堆中每个数都不小于大根堆中的最大值。枚举区间的起点，依次向后加入数，只需控制大根

堆中数的个数小于等于小根堆的个数。那么大根堆中最大的数就是中位数，大根堆中所有数的和就

是小于中位数的所有数的和。

怎么全是车。。

还是你...

http://hi.baidu.com/macaulish64/item/3f530048f38f611cfb896042

编译通过...├ 测试数据 01：答案正确...ms├ 测试数据 02：答案正确...ms├ 测试数据 03：答案正确...ms├ 测试数据 04：答案正确...ms├ 测试数据 05：答案正确...ms├ 测试数据 06：答案正确...259ms├ 测试数据 07：答案正确...274ms├ 测试数据 08：答案正确...290ms├ 测试数据 09：答案正确...306ms├ 测试数据 10：答案正确...368msAccepted 有效得分：100 有效耗时：1497ms

SBT....慢就慢吧，好理解，AC了就行！