莫隊

oi-wiki

核心思路：離線算法，把每次的詢問先記錄下來，按一定的順序排序，然後暴力從上一個區間轉移到下一個區間。

複雜度：

當 \(n\) ,\(m\) 同階時，塊長取 \(\sqrt n\) 時，複雜度為 \(o(n \sqrt n)\) ；

當 \(m < n\) 時，塊長取 \(\displaystyle \frac{n}{\sqrt{m}}\) 時，複雜度為 \(o(n \sqrt m)\) .

例題 小 z 的襪子

分析可見 oi-wiki ( /xyx

code

大數

如果直接求一個序列的答案，發現并不好求。于是考慮求以 \(l\) 為左端點（右端點類似）所造成的貢獻，顯然，當滿足 \(\displaystyle \frac{ s[r]−s[l−1]}{10^{n−r}}\equiv0\pmod{p}\)，就找到了一個合法的區間（\(s[i]\) 表示由前 \(i\) 個數和後 \(n−i\) 個 \(0\) 構成的數字）。這樣我們發現，假設我們已知一個區間的答案，可以做到 \(o(1)\) 移動一個機關的端點。而我們要求的，實際上就是區間中等于某個數的位置個數。可以将其離散化之後，用莫隊+桶維護。

\(\texttt{end.}\)