[bzoj 4542] [Hnoi2016]大数：莫队算法

为什么当时我认定这是一道字符串题，写了半个AC自动机，删掉，改成枚举+哈希？写完之后感觉很奇怪，怎么没用上p是素数这个假设？

考试的前天晚上还和学长讨论莫队算法来着……嗯，还讨论了主席树……

莫队算法是解决一类离线区间查询问题的算法。设序列长度为n，有m个查询。为了达到理想的时间复杂度，需要保证[l, r]能在$O(1)$的时间转移到[l, r+1]，[l, r-1]，[r-1, l]，[r+1, l]。把整个序列分成$\sqrt n$块，把左端点所在的块的序号作为第一关键字、右端点作为第二关键字，对询问排序，通过向相邻的区间转移，依次得到答案。时间复杂度是$O((m+n)\sqrt n)$。

知道了这道题可以用莫队来做，研究了一下。一开始，我的方案是这样的：分别维护区间的前缀、后缀对p取模后每种结果的数量。扩展后缀时，相当于把先前的每个数乘10加s，并把s模p加入。扩展前缀时，把整个区间看成十进制小数（取模结果不会变），于是乘10的逆元再加s，并把s模p加入。收缩的时候，把过程倒过来即可。把所有的数搬来搬去不太现实，所以维护一个线性函数h，数组的位置i实际上存储的是h(i)。注意整个区间既是前缀又是后缀。

诶？怎么没给p的数据范围？不管了，先写吧。然后就没有然后了……渐渐地，我自己都不知道自己在写什么了。现在我也发现这样空间似乎会爆。如果不管空间限制，这样应该是可行的？如果阅读本文的你有什么想法欢迎交流。

学习了CtrlCV的题解。维护所有后缀对p取模的结果，设为x[i]，令x[n] = 0（下标从0开始）。x[l]-x[r+1]等于s[l..r]乘10的幂。当p不等于2或5时，由于p和10互素，s[l..r]是p的倍数当且仅当x[l] = x[r+1]。当p等于2或5，这招就不灵了，但是但是可以判断个位数字；可以用莫队来做，也可以通过前缀和来做：

$$\Sigma_{i=l}^r(i-l+1)[\text{$s[i]$ mod $p$ = 0}] = \Sigma_{i=l}^ri[\text{$s[i]$ mod $p$ = 0}] - (l-1)\Sigma_{i=l}^r[\text{$s[i]$ mod $p$ = 0}]$$

要离散化！离散化的时候不要忘记x[n]。

在这里证一下莫队算法的复杂度。

对询问排序后，至多有m个查询和上一个查询在同一块中、$\sqrt n$个不在同一块中。如果两个相邻查询在同一块中，r指针递增，共$O(n\sqrt n)$，每次l指针变化不超过$\sqrt n$，共$O(m\sqrt n)$。如果两个相邻查询不在同一块中，每次r指针至多变化n，共$O(n\sqrt n）$，考虑所有这类情况，l递增，共$O(n)$。由于转移是$O(1)$的，所以指针变化次数与转移的总代价在同一个数量级。因此，莫队算法的时间复杂度是$O((m+n)\sqrt n)$。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
typedef long long ll;
char s[MAX_N+1];
bool f;
ll ans, p, x[MAX_N+1], t[MAX_N+1], h[MAX_N+1];
int top = 1, m, sz, od[MAX_N], blk[MAX_N], c[MAX_N+1]; // c[i] ~ 后缀i的计数器
struct Query {int fr, to;ll ans;
} Q[MAX_N];bool cmp(int i, int j)
{const Query& x = Q[i], & y = Q[j];return blk[x.fr] < blk[y.fr] || blk[x.fr] == blk[y.fr] && x.to < y.to;
}inline void inc(int i)
{ans += t[c[i]]++;
}inline void dec(int i)
{ans -= --t[c[i]];
}void solve_1()
{int cnt = 0, l = Q[od[0]].fr, r = l-1;for (int i = 0; i < m; ++i) {Query& q = Q[od[i]];while (r < q.to) {++r;if (s[r]%p == 0) {ans += r-l+1;++cnt;}}while (r > q.to) {if (s[r]%p == 0) {ans -= r-l+1;--cnt;}--r;}while (l > q.fr) {--l;if (s[l]%p == 0)++cnt;ans += cnt;}while (l < q.fr) {ans -= cnt;if (s[l]%p == 0)--cnt;++l;}q.ans = ans;}
}void solve_2()
{int l = Q[od[0]].fr, r = l;inc(r);for (int i = 0; i < m; ++i) {Query& q = Q[od[i]];while (r < q.to)inc(++r);while (r > q.to)dec(r--);while (l > q.fr)inc(--l);while (l < q.fr)dec(l++);q.ans = ans;}
}int main()
{int n = 0;scanf("%lld %s %d", &p, s, &m);int fr, to;bool f = 10%p == 0;for (int i = 0; i < m; ++i) {scanf("%d %d", &fr, &to);Q[i].fr = fr-1;Q[i].to = f ? to-1 : to;od[i] = i;}for (; s[n]; ++n)s[n] -= '0';h[0] = 0;for (ll i = n-1, t = 1; i >= 0; --i, t = t * 10 % p) {x[i] = (x[i+1] + s[i]*t%p) % p;h[top++] = x[i];}sort(h, h+top);top = unique(h, h+top) - h;for (int i = 0; i <= n; ++i)c[i] = lower_bound(h, h+top, x[i]) - h;sz = sqrt(n);for (int i = 0; i < n; ++i)blk[i] = i/sz;sort(od, od+m, cmp);if (f)solve_1();elsesolve_2();for (int i = 0; i < m; ++i)printf("%lld\n", Q[i].ans);return 0;
}