T134397
E:【题目名称】中位数
【方法1】
- 题目看不懂不写了。
复杂度】
-
O(0)
【预计状态】
- ？？？
【预计得分】
- 0pts
【方法2】
- 枚举每次操作的区间按题意模拟。
【复杂度】
-
O($爆炸$)
【预计状态】
- TLE+AC
【预计得分】
- 10~20pts
【方法3】
- 考虑特殊性质部分数据。
-
- 答案即输出样例:
- 直接输出1 3
-
-
- 直接输出
a_{l}
-
-
-
- 直接输出q行1 1
4.
a_{i} 只有1或2 - 最小值：
- 当其中有1时显然可以对它与一个相邻的组成的区间进行操作如下:
-
- 重复这个过程：
1\ 1\ 1\ 1[1\ 1][1\ 1] - 必然能达到全是1的情况
- 当其中没有1时 它全是2
- 所以只要判断询问区间是否有1即可
- 最大值：
- 先假设
r-l+1 \ge 3 - 如果这个数列里存在一个长度为3的区间满足它的中位数是2
- (比如这种区间:{1 2 2},{2,1,2}，就是1的个数为0或1的)
- 那么我们对它进行操作：一定会出现[2 2 2]，重复这个过程
- 以上述序列为例：
1\ 1\ 2\ 1\ 1\ 2\ 2\ 1\Rightarrow 1\ 1\ 2\ 1[2\ 2\ 2]1\Rightarrow 1[2\ 2\ 2]2[2\ 2\ 2]\Rightarrow [2\ 2\ 2]2\ 2\ 2\ 2\ 2 - 必然能达到全是2的情况
- 反之，若每一个长度为3的区间中1的个数均为2或3
- 那么所有区间的中位数都是1，所以预处理每个点与两个相邻的组成的区间的中位数
- 查询时判断存不存在中位数为2的区间即可！
- 用前缀和判断区间存不存在某个数每次查询
O(1) - 注意：当
r-l+1<3 时要特判！！！！！！！！
【复杂度】
-
O(1)$或$O(q)
【预计状态】
- TLE+AC+WA
【预计得分】
- 40pts
【方法4】
- 受到刚才思路的启发，可以发现：
- 最小值：
- 显然可以对 这个数列最小值与一个相邻的组成的区间 进行操作
- 重复这个过程，必然能达到全是最小值的情况
- 最大值：
- 我们对长度为3的 中位数最大的区间进行操作重复这个过程，
- 最终结果就是原来长度为3的 中位数最大的区间的中位数。
- 你可能会问，为什么要选长度为3的区间呢？
- 会不会存在一个更长的，中位数更大的区间呢？
- 答案:不会的。
- 因为对于任意一个长度为3的区间都至少有2个数小于你说的这个数
- 所以不会存在。
- 只需预处理每个点与两个相邻的组成的区间的中位数
- 查询时取最大值即可
- 要用st表
- 或者分块，线段树等奇奇怪怪的算法
- 再次注意：
- 当
r-l+1<3 时要特判！！！！！！！！
【复杂度】
- 暴力求最值
O(nq) - 分块，线段树等奇奇怪怪的算法
O(q\sqrt n)O(q\log(n)) - St表
O(n\log(n)+q)
【预计状态】
- 暴力求最值TLE+AC
- 分块，线段树等奇奇怪怪的算法AC
- St表AC
- 没特判WA+AC
【预计得分】
- 暴力求最值60pts
- 特判12~15的数据80pts
- 分块，线段树等奇奇怪怪的算法100pts
- St表100pts
- 没特判RPpts