目录
普通莫队
初遇——从暴力谈起
我们通过一道例题来讨论普通莫队。
题目链接。
观察数据范围，一个很直接的想法是：开一个数组 \(cnt\)，\(cnt_i\) 表示在询问的区间内数字 \(i\) 出现的次数。对于每一个询问，记询问区间左端点为 \(lt\)，询问区间右端点为 \(rt\)，对于 \(i\in [lt,rt],cnt_{a_{i}}\leftarrow cnt_{a_{i}}+1\)，最后扫描一遍 \(cnt\) 数组统计 \(cnt\) 数组中有几个位置不为 \(0\)，统计的结果即为这次询问的答案。记给定的 \(a\) 数组中最大的数为 \(K\)，这个算法的时间复杂度在最坏的情况（即每个询问的左端点都是 \(1\)，右端点都是 \(N\)）下为 \(O(NQK)\)，无法通过本题。
接下来我们考虑如何优化这个算法。
首先，对于 \(i\in [lt,rt]\)，如果 \(cnt_{a_{i}}=0\)，则说明 \(a_{i}\) 在询问的区间中第一次出现，答案加一，这样省去了扫描 \(cnt\) 数组的过程，在最坏的情况下时间复杂度降为 \(O(NQ)\)，但是效率还是不够高。
接下来我们看几个询问：
1 5
2 6
5 7
...
我们注意到，这几个询问的区间有重复部分，解决每个询问时都会重复扫描重复部分，很浪费时间。于是，我们可以使用两个指针 \(l\) 和 \(r\)，对于一个询问，我们不再直接扫描对应的区间，而是将 \(l\) 指针移动到对应的左端点，将 \(r\) 指针移动到对应的右端点，并且仅在 \(l\) 指针或 \(r\) 指针移动时对 \(cnt\) 数组和答案进行修改。
于是我们可以写出如下代码：
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,a[30005],m,cnt[1000005],now,l=1,r=0,lt,rt;
void add(int x){
if(!cnt[a[x]]) now++;
cnt[a[x]]++;
}
void del(int x){
cnt[a[x]]--;
if(!cnt[a[x]]) now--;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++){
cin>>lt>>rt;
while(l<lt) del(l++);
while(l>lt) add(--l);
while(r<rt) add(++r);
while(r>rt) del(r--);
cout<<now<<endl;
}
return 0;
}
困境——乱跑的指针
当一个询问的左端点和右端点与上一个询问的左端点与右端点差距过大时，就会出现 \(l\) 指针和 \(r\) 指针在数列上乱跑的情况，无法保证效率。
例如当 \(N=30000\) 时的这几个询问：
1 2
29999 30000
3 4
29997 29998
...
这时， \(l\) 指针和 \(r\) 指针先从序列开头跑到了序列末尾，又从序列末尾跑到了接近序列开头的位置，然后又跑到了接近序列末尾的位置。
那么如何提高指针移动的效率呢？
我们观察到，指针的低效移动是由询问左右端点的无序性引起的，所以我们可以把询问离线，并将数列分块。按照左端点所处的块的位置升序排序，如果左端的所处的块位置相同，则按照右端点升序排序。这样，就在保证了左端点比较有序也保证了右端点比较有序，从而提高了指针的移动效率。
代码如下：
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,a[30005],m,cnt[1000005],now,l=1,r=0,L[30005],R[30005],pos[30005],t,ans[200005];
struct node{
int l,r,id;
}q[200005];
inline bool cmp(node x,node y){
if(pos[x.l]==pos[y.l]) return x.r<y.r;
return pos[x.l]<pos[y.l];
}
inline void add(int x){
if(!cnt[a[x]]) now++;
cnt[a[x]]++;
}
inline void del(int x){
cnt[a[x]]--;
if(!cnt[a[x]]) now--;
}
signed main(){
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
t=sqrt(n);
for(int i=1;i<=t;i++){
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if(R[t]<n){
t++;
L[t]=R[t-1]+1;
R[t]=n;
}
for(int i=1;i<=t;i++){
for(int j=L[i];j<=R[i];j++){
pos[j]=i;
}
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
for(int i=1;i<=m;i++){
while(l<q[i].l) del(l++);
while(l>q[i].l) add(--l);
while(r<q[i].r) add(++r);
while(r>q[i].r) del(r--);
ans[q[i].id]=now;//注意，排序只有询问的顺序可能会改变，所以应该将答案存在ans[q[i].id]而不是ans[i]
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
优化——顺路而为之
我们考虑一种排序方式：
对于左端点所处的块不同的询问，按左端点升序排序。对于左端点所处的块相同的询问，若这个块是的编号是奇数，则按右端点升序排序，否则按右端点降序排序。
按照这样的方式排序后，\(r\) 指针能在处理完奇数块的询问后，可以在返回的途中顺路处理偶数块的询问，减少 \(r\) 指针的移动次数，从而提高效率。
代码如下：
bool cmp(node x,node y){
if(x.l/t!=y.l/t) return x.l<y.l;
if((x.l/t)&1) return x.r<y.r;
return x.r>y.r;
}
带修莫队
咕咕咕