houpingze 的博客

膜拜zqs,sx,zlt,ymw,qyh官方博客

zqsAKIOI

由于 $ m\leq 5\times10^4 $ ,时间限制 $ 5 \text{s} $ ,我们考虑分块(什

具体思路:

$ \sqrt{n} $ 一块,每块用一个 $ \text{vector} $ 维护当前块的递增有序序列,每次询问的时候,对于零散块,我们可以暴力统计。对于每一个完整的块,由于我们有有序的 $ \text{vector} $ ,可以使用 $ \text{lower\_bound} $ 函数计算严格小于 $ v $ 的数的个数。

最后按照题意单点修改 $ a_p $ 即可,注意此时块内和 $ a $ 数组都要修改,块内还需要重新排序。具体实现:

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})} $


2021-08-23 18:09:15 in 题解