首页 > 代码库 > 莫队算法良心讲解
莫队算法良心讲解
问题：有n个数组成一个序列，有m个形如询问L, R的询问，每次询问需要回答区间内至少出现2次的数有哪些。
朴素的解法需要读取O(nm)次数。如果使用STL的Map来保存出现的次数，每次需要O(nmlogn)的复杂度。有没有更快的方法呢？
注意到询问并没有强制在线，因此我们可以使用离线方法。注意到一点，如果我们有计算完[L, R]的map，那么[L - 1, R]、[L + 1, R]、[L, R - 1]、[L, R + 1]都能够在O(logn)的复杂度得出。是否能安排适当的询问顺序，使得每次询问都能用上上次的map，那么我们将可以在更优的复杂度完成整个询问。
那如何安排询问呢？一种办法是按照左端点排序，再按照右端点排序。排序的复杂度是O(mlogm)。左端点移动次数仅为为O(n)，但右端点每个询问移动O(n)，共有m个询问，故总移动次数为O(nm)，一共移动O(mlogm + nm)，再乘上STL的O(logn)，运行时间上界并没有减少。
莫队算法是解决上述问题的好方法。莫队算法认为，按照左端点排序后，左端点移动总得少，但是右端点移动的次数则多得多。如果适当减少右端点移动次数，即使稍微增多一点左端点移动次数，在总的复杂度上看，也是划算的。
莫队算法首先将整个序列分成√n个块（只是概念上分的块，实际上我们并不需要存储除了块大小以外的任何东西），将每个询问按照块序号排序（一样则按照右端点排序）。之后，我们从排序后第一个询问开始依次解决子问题。
int len;
struct Query{ int L, R, ID, block; Query(){} Query(int l, int r, int ID):L(l), R(r), ID(ID){ block = l / len; } bool operator < (const Query rhs) const { if(block == rhs.block) return R < rhs.R; return block < rhs.block; }}queries[maxm];map<int, int> buf;inline void insert(int n){
if(buf.count(n))
++buf[n];
else
buf[n] = 1;
}inline void erase(int n){
if(--buf[n] == 0) buf.erase(n);
}int A[maxn]; // 原序列queue<int> anss[maxm]; // 存储答案int main(){int n, m; cin >> n; len = (int)sqrt(n); for(int i = 1; i <= n; i++){ cin >> A[i]; } cin >> m; for(int i = 1; i <= m; i++){ int l, r; cin >> l >> r; queries[i] = Query(l, r, i); } sort(queries + 1, queries + m + 1); int L = 1, R = 1; buf[A[1]] = 1; for(int i = 1; i <= m; i++){ queue<int>& ans = anss[queries[i].ID]; while(R < queries[i].R) insert(A[++R]); while(R > queries[i].R) erase(A[R--]); while(L < queries[i].L) erase(A[L++]); while(L > queries[i].L) insert(A[--L]); for (map<int, int>::iterator it = buf.begin(); it != buf.end(); ++it){ if(it->second >= 2){ ans.push(it->first); } } } for(int i = 1; i <= m; i++){ queue<int>& ans = anss[i]; while(!ans.empty()){ cout << ans.front() << ‘ ‘; ans.pop(); } cout << endl; }}
尽管分了块，但是我们可以对所有的“询问转移”一视同仁。上述的代码有三个需要注意的地方。一是insert和erase，这里在插入前判断了是否存在、插入后判断是否为0。这不是必须的（insert时会将新节点初始化为0，erase为0后对处理答案不影响）；二是区间变化的顺序，insert最好放在前面，erase最好在后面（想一想，为什么）；三是insert总是使用前缀自增自减运算符，erase总是用后缀运算符。
莫队的时间复杂度如何呢？我们将问题分类讨论。
当前询问与上一询问左端点处在同一块，那么左端点移动为O(n0.5)。虽然右端点移动可能高达O(n)，但是整一块询问的右端点移动距离之和也是O(n)（想一想，为什么）。因此整块移动为O(m0.5) × O(n0.5) + O(n)，一共有m0.5块，时间复杂度为O(mn0.5+nm0.5)。
当询问与上一询问左端点不处于同一块，那么左端点移动为O(n0.5)，但右端点移动则高达O(n)。幸运的是，这种情况只有O(n0.5)个，时间复杂度为O(n1.5)。
总的移动次数为O(n1.5+m0.5n+mn0.5)，因为使用map，总的时间复杂度还要在总的移动次数上再乘一个O(logn)。
莫队算法良心讲解