好久不写SBT，3遍才对……

SBT的速度：

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

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

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

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

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

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

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

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

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

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

以前写的Treap：

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

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

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

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

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

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

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

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

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

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

看来还是要快一点的啊……

8楼的

h[j]（ji时) 表示 中不大于a（小于等于）的个数 减 中比a大的个数

如果遇到相同的两个数怎么办

如4 1 2 2 2 13 0

2是算大于2的还是小于2的，还是不管

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用线段树+离散化（没有重复的高度）做的，不快但是好懂

谁有AC，C++的好方法，介绍一下，不用太秒杀了，瞄一下就可以了

。。。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

没用N^2的方法，因为考虑到比赛时很难想到那样的方法，而更容易想到的是堆优化，所以用了堆，这题可以作为一道不错的小跟堆-大跟堆练习题。

想过用平衡二叉树的方法（还不会，囧），只是调整树实在。。。想想就害怕

200 300

432414 81167 103925 195235 158451 157126 424494 247044 57047 151447 463884 179133 13941 468883 404346 27613 154065 85719 67456 416026 435048 15158 178309 120329 145406 289311 452740 78173 194435 409782 397675 139286 468405 209795 173343 310762 175760 93557 447813 130114 357470 382164 27682 117217 150737 404099 391762 189171 283770 52573 278645 399514 237450 213354 174128 292768 158921 20089 136022 418510 266259 441815 185264 16540 387996 229404 328646 446392 193985 368616 194736 354403 316230 334408 437800 343519 458599 448557 75277 36482 105903 442777 434357 361586 163588 230422 108246 422377 394237 269362 434293 234034 461483 42618 466476 419991 364170 466858 386462 305223 408056 60790 38848 203005 136521 376256 146559 168605 331620 99727 68417 413951 254476 205743 214685 8143 199130 63102 260146 6910 224699 185144 350361 216690 39129 281893 76273 338801 261303 427599 312820 32309 386646 48822 320929 53888 454866 315914 182442 132603 278295 420336 225838 45007 146822 298990 90501 208057 251998 220278 286003 116170 455203 327165 317752 30475 256804 410687 24675 435431 275981 401866 4885 204940 272597 207656 311871 347813 127238 71543 129795 9929 133877 360744 308106 275401 295783 112132 373412 97298 166576 242286 40269 441668 285255 220687 336995 329391 174512 50299 379363 311172 123565 0 301966 48341 302206 142969 322854 399627

46 193

114 122

113 159

31 93

71 88

61 158

125 190

99 114

97 119

18 117

4 172

大根堆 + 小根堆 + scanf() == AC ！！！！！！！！！！！！！！！！！

cin 太慢！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

N^2找中位数果然神奇

为什么老是 栈溢出

谁能给几组数据看看谢谢啊

事实上，这题的最佳方法并非是高级的数据结构。只要用n^2处理出每个区间的答案即可。大家最好不要随便抄袭题解里的算法（两个堆实在是太慢了）。

a是读入的高度

首先，枚举每个数a。向左向右扫描，那么这个数是中位数的充要条件是 比它大的数的个数与比它小的个数相差不超过一。所以向左向右求出，

h[j]（ji时) 表示 中不大于a（小于等于）的个数 减 中比a大的个数

那么,a为[l,r]的中位数的 充要条件 是

( [L,R]中有奇数个数,且h[R]-h[L]=1 ) 或 ( Ll,R]中有偶数个数,且h[R]-h[L]=0 )

对于每个l(1

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我的线段树＋离散看来比楼下的慢了好多啊！

本题就是求Li到Ri段每个数与该段中位数差的绝对值之和（很容易想到当统一调整到中位数的高度时，总时间最少），由于每次车展互不影响，所以可以逐一处理。

先预处理，然后O（1）输出m次。

预处理：

线段树（离散（快排需要O(nlogn)的时间））记录该段插入已点的个数。

外面两重循环表示处理i到j段（O(n^2)）。

在线段树中插入点需要O(logn)的时间。

算出每段的中位数（logn），然后求该段每个数与中位数差的绝对值之和（O(1)）。

总的时间复杂度是O(n^2logn)。

我用小号（鄙视我吧！我也和你们一起鄙视）试过了最最快的（我所能想到的）O(nlogn+mn)的方法，还是在最后一个点超时，所以O(mn)的算法看来是没希望了！

谁知道O(n^2)的算法？能给出具体方法吗？

10 10

28 5 10 16 24 14 7 15 20 0

1 7

2 4

9 10

9 10

8 9

3 6

7 10

3 9

4 7

6 10

ans:222

数据背后是20+次的提交和第20+ +次的AC

..前面有人说维护两个堆的..我说的详细点..

首先每次加一个元素进入大根堆.如果 大根堆的元素个数-1>小根堆的元素个数.那么把大根堆堆顶的元素加入小根堆.

这样就保证了小根堆的元素个数总是等于或者比大根堆的元素个数少1.

然后再比较小根堆堆顶元素与大根堆堆顶元素.如果小根堆堆顶元素小于大根堆堆顶元素.那么把大根堆堆顶元素加入小根堆.把小根堆堆顶元素加入大根堆.这样就可以保证小根堆中所有元素都不小于大根堆中的元素.于是大根堆堆顶元素就是中位数..

C++选手注意不要用cin,cout....

4次...

第一次(比赛)

没有用qword...用了longint...

编译通过...

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

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

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

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

测试数据05：运行时错误...| 错误号: 216 | 存取非法

测试数据06：运行时错误...| 错误号: 216 | 存取非法

测试数据07：运行时错误...| 错误号: 216 | 存取非法

测试数据08：运行时错误...| 错误号: 216 | 存取非法

测试数据09：运行时错误...| 错误号: 216 | 存取非法

测试数据10：运行时错误...| 错误号: 216 | 存取非法

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

Unaccepted 有效得分：40 有效耗时：346ms

第2次...

朴素的查找算法...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：60 有效耗时：994ms

第3次...

改进的查找算法...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第4次...

传说中的O(N^2)算法...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第67个AC...荣幸地将P1459的通过率提升了1个百分点【从19%提升至20%】

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

爽！！！

时隔多年,一次AC!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Flag 　　Accepted

题号 　　P1459

类型(?) 　　其它

通过 　　50人

提交 　　261次

通过率 　　19%

难度 　　1

第50个AC的，哈哈

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

终于AC了，用一个快排记录,实现平衡树，再用适时记录一下就行了,在预处理时搞定的话,就不会超时了.