RainAir
My OI Blog
RainAir
[HEOI2016/TJOI2016]排序

题目描述

题目链接

对一个长度为 $n$ 的排列进行 $m$ 次如下操作:

  1. 将区间 $[l,r]$ 中的数字升序排序。
  2. 将区间 $[l,r]$ 中的数字降序排序

最后输出位置 $p$ 的数字。

其中 $1 \leq n,m \leq 10^5$

解题报告

发现询问只有一组,我们可以考虑二分答案。

考虑二分答案 $p$ 表示该输出的答案。因为这是一个排列,所以我们可以把小于 $p$ 的数标记为 $0$ ,大于 $p$ 的数标记为 $1$ ,线段树维护一下区间覆盖和求和,最后检验一下位置是 $0$ 还是 $1$ 就可以了。

升序排序相当于把 $1$ 放到后边,降序排序则是放到前边。

如果二分后位置是 $0$ 的话显然正确答案比二分的答案要更大,是 $1$ 的话则要小,因为二分成立当且仅当这个位置的数是 $1$。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/50
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

[HEOI2016/TJOI2016]排序
题目描述 题目链接 对一个长度为 $n$ 的排列进行 $m$ 次如下操作: 将区间 $[l,r]$ 中的数字升序排序。 将区间 $[l,r]$ 中的数字降序排序 最后输出位置 $p$ 的数字。 其中 $1 \le…
扫描二维码继续阅读
2018-10-11
标签
近期评论