1. 题目

传送门= ̄ω ̄=

更新:突然发现LUOGU上有这题(LUOGU - 2617),可以木有权限号刷~传送门= ̄ω ̄=

题目大意:

给你一个序列,要求资磁两个操作:

  • 将某一个位置的数字改变
  • 询问一段区间内第k小的数字

操作数和序列长度均在10000的范围内,无多组数据。

2. 题解

首先如果不带修改的区间第k小(大)问题我已经写过两个题解了:

如果带修改怎么办呢?

  1. 听说可以树状数组套主席树$O(mlog_2^2n)$做,然而我不会QvQ
  2. 借鉴上面的二分答案套线段树的静态k小数做法,我们可以把线段树对应的那一段段数组区间换成一颗颗splay来资磁修改!

具体思路懒得讲了,上面那篇博客(二分套线段树)中讲过惹。。。

算法复杂度是$O(mlog_2^3n)$

直接放代码吧(我懒你咬我啊?),我会附上注释的=。=

PS:没想到这玩意也不难打,一开始以为至少两三百行,结果最后才140多行,而且还一遍AC惹!爽啊♂~

代码: