题解 P3332 【[ZJOI2013]K大数查询】

这题线段树套线段树整整交了2页半，心态都炸了 QwQ 这道题线段树套线段树的做法已经有神仙讲过了，也就是权值线段树套区间线段树。 由于线段树常数巨大，再加上我自带的三倍常数，这题卡了几个小时的常数也没能卡过去，然后想到树状数组常数巨小，于是考虑使用树状数组代替外层的权值线段树。 显然插入操作树状数组可以轻松解决，考虑如何完成询问操作，也就是在权值树状数组上二分。 我们先考虑寻找第K小值，根据树状数组的性质可以想到下面这种二分方法： 我们按二进制从高位到低位去二分所找位置在这一位的数组，进行以下代码所示的操作。 ```cpp int now = 0; //表示现在二分到的数字 ll sum = 0; //表示从1到now的和 for (register int i = 16; i >= 0; i--) { int nex = now | 1 << i; //判断这个位置是否能为1 if (nex > n) { //显然这个数字不可能比n大 continue; } ll tmp = a[nex].Query(l, r); //求出 if (tmp + sum >= rank) { continue; } now = nex; sum += tmp; } ``` 暂未完成 QwQ