题意：
给定一个序列\(a\)，定义一次操作选择序列中一个元素\(a[i]\)， 使\(a_i = \lfloor \frac{a_i}{2} \rfloor\)，其中\(a_i\)为当前序列中的最大偶数，若没有则是最大奇数。
有\(q\)组询问，每次给定\(k, l, r\)分别表示操作次数和操作区间，每次回答操作完成后区间中的\(Max\)，询问间互相独立。
\(n\le10^4, a_i\le 10^9, 1\le l\le r \le n,k\le 10^9\)
Solution：
\(Hint1\) 不管奇数还是偶数，操作次数始终是\(\log{a_i}\)次，所以一共能操作\(n * \log{a_i}\)次
\(Hint2\) 考虑一次询问的\(k=10^9\),区间为\([1,n]\)次的情况，如果那么每次一操作的元素下标是一定的，令该序列为\(Operations\)
\(Hint3\) 考虑获取这个序列，优先队列模拟即可
\(Hint4\) 考虑任意选择区间，\(k=10^9\)，容易知道此时的操作序列一定为\(Operations\)的一个子序列，令该序列为\(SubOperations\)， 那随着\(k\)缩小，新的操作序列一定为\(SubOperations\)的一个前缀
\(Hint5\) 考虑以建立\(|Operations|\)棵线段树，每棵线段树内部维护信息为\(cnt和Max\)，内部下标为\([1, n]\)，那么第\(i\)棵线段树中\(cnt\)记录执行到第\(i\)次操作时对区间的操作次数，那么\(Max\)就是维护一个区间最大值，每次操作都是单点修改，只会改变一条链，故建立可持久化线段树。
\(Hint6\) 考虑解决询问，我们只要每次二分这\(|Operations|\)个版本，找到第一个区间内操作次数\(\ge k\)的版本即可，然后输出区间最大值即为答案
时间复杂度\(O(qlog^2+n\log^2)\)，空间复杂度\(O(nlog^2)\)
比题解低能，但是思想简单，写法简单，但是没写出来
标签：Even,cnt,int,Max,线段,rtv,序列,23Nowcoder6,id From： https://www.cnblogs.com/Fighoh/p/17607205.html