介绍个最劣解 \(O(m\sqrt n+n\sqrt n+n\alpha(n)\ln n)\) 做法。
首先令 \(b_i\gets a_i-1\)，区间 \([l,r]\) 的答案就是：
\[r-l+1+\sum\limits_{k=l}^r\text{mex}_{i=l}^r\left\lfloor\frac{b_i}{k}\right\rfloor \]考虑如何动态维护后面那个式子。我们对每一个 \(k\in [1,n]\) 维护一个大小 \(n/k\) 的 bitset，代表所有 \(b_i/k\) 的值，最低位的 \(0\) 就是 \(k\) 对应的 \(\text{mex}\)。
加入一个 \(b_i\) 的时候考虑所有 \(b_i/k\) 的值，不难发现只有 \(O(\sqrt n)\) 种取值，于是可以分成 \(O(\sqrt n)\) 个区间修改，每次修改形如 \((l,r,x)\)，代表往 \(l\) 到 \(r\) 每个 bitset 中插入数 \(x\)。
因为 \(n\) 个 bitset 的总大小不超过 \(n\ln n\)（调和级数），所以如果我们每次修改 \((l,r,x)\) 都能找到一个是 \(0\) 的位，把这位换成 \(1\)，并不访问别的 \(1\) 的话，这个复杂度就是正确的。于是不难想到对每个 \(x\) 维护一个并查集，这样就可以从一个位置 \(p\in[l,r]\) 迅速跳到下一个第 \(x\) 位为 \(0\) 的 \(p'\) 了。
然后我们在跳 \(p\) 的时候需要动态维护 \(p\) 的 bitset 的 \(\text{mex}\)，由于只有插入没有删除，这显然可以均摊 \(O(n\ln n)\) 维护。得到这个 \(p\) 的权值后，就只需要一个单点修改 \(O(1)\) 的数据结构来维护区间和了。显然分块可以做到 \(O(1)-O(\sqrt n)\)。于是就得到了 \(O(m\sqrt n+n\sqrt n+n\alpha(n)\log n)\) 的优秀做法。
代码，自以为写得很清晰。
标签：ln,text,Ynoi2015,sqrt,mex,bitset,维护,回来 From： https://www.cnblogs.com/Ender32k/p/17680134.html