4 条评论
-
tigertang LV 10 @ 2015-03-07 22:26:27
这不是一眼题么
-
@ 2015-02-26 23:46:56
我想说为什么我又又又又被卡常数了，明明离散化之后可持久化线段树就可以做了，询问在离散化之后代表的那个区间二分一下就好了啊，明明效率就是nlogn+3mlogn，这也可以跪。。。我也是醉了额。。。。。
-
@ 2015-02-27 10:26:04
卡常数确实略无聊………………
但是说实话…………线段树确实比树状数组慢了很多啊…………
-
-
@ 2015-02-19 21:17:46
没错你被卡常数了。
-
@ 2015-02-19 18:48:59
是这样的……
首先这道题可以离线。（在线我并不会低于log^2的做法。
然后就显然了。按照权值排序，每个询问拆成两个。
用一个树状数组就够了。-
@ 2015-02-19 20:42:23
什么叫离线？。。。。。。
不要鄙视我。。。 -
@ 2015-02-19 20:59:55
可持久化在线不就是logn的吗？不知道是不是被卡常数了，TLE三个点
-
@ 2015-02-19 21:12:07
离线做法见题解……
O(mlogm)。
测试数据 #0: Accepted, time = 0 ms, mem = 48924 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 48924 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 48924 KiB, score = 10
测试数据 #3: Accepted, time = 81 ms, mem = 48920 KiB, score = 10
测试数据 #4: Accepted, time = 124 ms, mem = 48920 KiB, score = 10
测试数据 #5: Accepted, time = 608 ms, mem = 48920 KiB, score = 10
测试数据 #6: Accepted, time = 694 ms, mem = 48920 KiB, score = 10
测试数据 #7: Accepted, time = 1006 ms, mem = 48924 KiB, score = 10
测试数据 #8: Accepted, time = 1080 ms, mem = 48920 KiB, score = 10
测试数据 #9: Accepted, time = 1236 ms, mem = 48920 KiB, score = 10
Accepted, time = 4859 ms, mem = 48924 KiB, score = 100 -
@ 2015-02-21 16:10:40
离线就是读入所有询问以后一并处理。
-
- 1
