| 题目名称 | 1763. [国家集训队2012]middle |
|---|---|
| 输入输出 | nt2012_middle.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 1024 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：35， 提交：74， 通过率：47.3% | ||||
 ┭┮﹏┭┮ |
100 | 3.474 s | 8.48 MiB | C++ |
 846047746 |
100 | 4.926 s | 8.17 MiB | C++ |
 AntiLeaf |
100 | 5.199 s | 98.22 MiB | C++ |
 Narcissus |
100 | 5.537 s | 0.62 MiB | C++ |
|
Narcissus |
100 | 5.591 s | 0.56 MiB | C++ |
 FoolMike |
100 | 5.701 s | 382.90 MiB | C++ |
 niconicoqaq |
100 | 5.714 s | 8.71 MiB | C++ |
|
哒哒哒哒哒！ |
100 | 5.837 s | 23.77 MiB | C++ |
 徐心雨 |
100 | 5.904 s | 8.17 MiB | C++ |
 Hzoi_Ivan |
100 | 6.253 s | 12.83 MiB | C++ |
| 关于 middle 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
才两个log，常数有这么大吗？$O(nlogn+qlog^{2}n)$
| ||||
|
写代码时头脑最好清楚些，否则写时犯的错很难调出来，而且不好拍出来。。。我每一次都要拍几百组才能拍出错23333。
| ||||
|
脑残错误调了两个多小时，我没救了= =
| ||||
|
无法逃离的大常数……
| ||||
|
为什么我的常数总是这么大TUT
丽洁只给了五组数据（这里的2~6），余下的是我自己造的 linux下一定要注意下标-1的问题，因为这个问题在windows下很可能显示不出来……另外，对NODE类重载加号来实现线段树的区间信息合并（这样不管查询什么都只需要写一个query）是一个有趣的思路，但它貌似和“下标-define表示法”风格不太一致……所以就这样了 | ||||
|
我会使用一些方式强制你在线
 好残暴！ 天一阁
2014-10-23 18:08
1楼
| ||||
核糖核酸
真呆菌
cstdio1763. [国家集训队2012]middle
★★★☆ 输入文件：nt2012_middle.in
输出文件：nt2012_middle.out
简单对比时间限制：3 s 内存限制：1024 MiB
middle(陈立杰)
时间限制：3.0s 内存限制：1.0GB
【大意】
一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。
回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。
位置也从0开始标号。
我会使用一些方式强制你在线。
【输入格式】
第一行序列长度n。
接下来n行按顺序给出a中的数。
接下来一行Q。
然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。
接下来n行按顺序给出a中的数。
接下来一行Q。
然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。
【输出格式】
Q行依次给出询问的答案。
【数据规模和约定】
0:n,Q<=100
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000
【样例输入】
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
【样例输出】
271451044
271451044
969056313
271451044
969056313