zqsAKIOI

由于 $ m\leq 5\times10^4 $ ，时间限制 $ 5 \text{s} $ ，我们考虑分块（什 具体思路： $ \sqrt{n} $ 一块，每块用一个 $ \text{vector} $ 维护**当前块的递增有序序列**，每次询问的时候，对于零散块，我们可以暴力统计。对于每一个完整的块，由于我们有有序的 $ \text{vector} $ ，可以使用 $ \text{lower\_bound} $ 函数计算**严格小于** $ v $ 的数的个数。 最后按照题意单点修改 $ a_p $ 即可，注意此时块内和 $ a $ 数组都要修改，块内还需要重新排序。具体实现： ```cpp int t=a[p]; a[p]=u*k/(r-l+1); *lower_bound(vc[id[p]].begin(),vc[id[p]].end(),t)=a[p]; sort(vc[id[p]].begin(),vc[id[p]].end()); ``` 其中 $ id_i $ 表示 $ a_i $ 所在的块下标， $ vc_i $ 里的元素是块 $i$ 的有序序列。 总体时间复杂度： $ \mathcal{O(m \sqrt{n} \log \sqrt{n})} $