莫队算法
概述
莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。
例题
Description：
有n个数字，给出k，以及m个查询。每次查询的格式是L,R，求L~R（左闭右闭）这个区间内数字的出现次数刚好是k的数字种数。
Example input：
5 2 3
1 2 3 2 2
1 2
2 4
1 5
Example output：
0 //没有
1 //2
0 //没有（2太多了，也不算）
解法
首先可以考虑暴力，每次询问L~R的时候枚举，时间复杂度O(n*m)。但是这里要是暴力能过我还说什么莫队算法呢？(orz...)
假设一开始，指针区间(0,0)，对于一个查询，我们将指针Left逐步更新成新的L，Right更新成新的R。
比如一开始Left=2,Right=3，而L=1,R=5，那么我们把Left--，并且把新的Left位置上的数字出现次数+1，Right++，把新的Right位置上的数字出现次数+1，直到Right=5为止
remove(x){ //把x位置的数字加入进来
cnt[num[x]]++;
if(cnt[num[x]] == k)
ans++;
}
add(x){ //把x位置的数字移出去
cnt[num[x]]--;
if (cnt[num[x]] == k - 1)
ans--;
}然后以上面题目为例；这种方法需要离线处理，我们同理来看一下解法：
Left = Right = 0;
ans=0;
for u = 1...m {
while (Left < L[u])
remove(Left++);
while (Left > L[u])
add(--Left);
while (Right < r[u])
add(++Right);
while (Right > r[u])
remove(Right--);
print ans;
}分析一下时间复杂度，从Left和Right的移动量来分析：每一个新的询问，Left和Right的移动量最大都会是O(N)，所以这样子的方法时间复杂度仍然是O(N*M)，但是莫队算法的核心就是由这么一个算法转变过来的，下面介绍一下如何用莫队算法解决这道题。
首先，对询问进行分块，m个询问，L和R的范围都在n以内，我们可以根据L和R的大小来对询问进行分块，假设n=9，并且有以下的询问：
2 3
1 4
4 5
1 6
7 9
8 9
5 8
6 8
对于n=9，我们以sqrt(n)为每个块block的大小，这里block=3，那么我们把1~3分成一组、4~6、7~9，对于每一个询问(L,R)，我们以L的范围来决定这个询问在哪个块，然后每一个单独的块内，我们让R更小的排在前面，那么上面的询问就分成：
(2,3)、(1,4)、(1,6)和(4,5)、(5,8)、(6,8)和(7,9)、(8,9)。这一步的排序操作代码：
public static class cmp implements Comparator<Query> {
public int compare(Query x,Query y) {
if((x.L / block) != (y.L / block))//不同块时
return x.L / block - y.L / block;
return x.R - y.R;//同一块内时
}
}经过分块之后，时间复杂度达到了O(nlogn)，这就是莫队算法，具体的证明过程可以看网上的文章
AC代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Query {
int l,r,id;
long a,b;
Query(int L,int R,int id) {
this.l = L;
this.r = R;
this.id = id;
}
}
public class Main {
static long ans = 0;
static int n,m,block;
static long[] cnt = new long[50001];
static int[] arr = new int[50001];
static int[] pos = new int[50001];
static Query[] q;
public static class cmp implements Comparator<Query> {
public int compare(Query x,Query y) {
if(pos[x.l] == pos[y.l])
return x.r - y.r;
return x.l - y.l;
}
}
public static class cmp_id implements Comparator<Query> {
public int compare(Query x,Query y) {
return x.id - y.id;
}
}
static void init() {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
q = new Query[m + 1];
for(int i = 1;i <= n;i++)
arr[i] = cin.nextInt();
block = (int) Math.sqrt(n);
for(int i = 1;i <= n;i++)
pos[i] = (i - 1) / (block + 1);
for(int i = 1;i <= m;i++) {
int l = cin.nextInt();
int r = cin.nextInt();
q[i] = new Query(l,r,i);
}
}
static void solve() {
for(int i = 1,l = 1,r = 0;i <= m;i++) {
while(r < q[i].r)
update(++r,1);
while(r > q[i].r)
update(r--,-1);
while(l < q[i].l)
update(l++,-1);
while(l > q[i].l)
update(--l,1);
if(q[i].l == q[i].r) {
q[i].a = 0;
q[i].b = 1;
continue;
}
q[i].a = ans - (q[i].r - q[i].l + 1);
q[i].b = (long)(q[i].r - q[i].l + 1) * (q[i].r - q[i].l);
long k = gcd(q[i].a,q[i].b);
q[i].a /= k;
q[i].b /= k;
}
}
private static void update(int x,int add) {
ans -= sqr(cnt[arr[x]]);
cnt[arr[x]] += add;
ans += sqr(cnt[arr[x]]);
}
public static void main(String[] args) {
init();
Arrays.sort(q,1,q.length,new cmp());
solve();
Arrays.sort(q,1,q.length,new cmp_id());
for(int i = 1;i <= m;i++)
System.out.println(q[i].a + "/" + q[i].b);
}
private static long sqr(long x) {
return x * x;
}
private static long gcd(long a,long b) {
return b == 0 ? a : gcd(b,a % b);
}
}莫队算法
莫队的精髓就在于，离线得到了一堆需要处理的区间后，合理的安排这些区间的计算次序以得到一个较优的复杂度
复杂度分析
- 分块相同时，右端点递增是O(N)的，分块共有O(N^0.5^)个，复杂度为O(N^1.5^)
- 分块转移时，右端点最多变化N，分块共有O(N^0.5^)个，复杂度为O(N^1.5^)
- 分块相同时，左端点最多变化N^0.5^，分块转移时，左端点最多变化2N^0.5^ ，共有N个询问，复杂度为O(N^1.5^)
普通莫队模板
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Query {
int l,r,id;
long a,b;
Query(int L,int R,int id) {
this.l = L;
this.r = R;
this.id = id;
}
}
public class Main {
final static int N = 1 << 21;
static long nowAns = 0;//当前答案
static int n,m,block;
static long[] cnt = new long[N];
static long[] ans = new long[N];//记录每个答案
static int[] arr = new int[N];//数组
static Query[] q = new Query[N];//询问
public static class cmp implements Comparator<Query> {
public int compare(Query x,Query y) {
if(x.l / block == y.l / block)
return x.r - y.r;
return x.l - y.l;
}
}
public static void remove(int x) {
//根据题目添加
}
public static void add(int x) {
//根据题目修改
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int l = 0,r = -1;
n = cin.nextInt();//数组长度
m = cin.nextInt();//询问次数
block = (int) Math.sqrt(n);//每块的大小
for(int i = 0;i < n;i++) {
arr[i] = cin.nextInt();
}
for(int i = 0;i < m;i++) {
int tmp_l = cin.nextInt();
int tmp_r = cin.nextInt();
q[i] = new Query(tmp_l - 1,tmp_r - 1,i);//减1是为了将询问转换为下标
}
Arrays.sort(q,0,m,new cmp());//sort是左闭右开的区间
for(int i = 0;i < m;i++) {
while(l < q[i].l) remove(l++);//移出数字
while(l > q[i].l) add(--l);//加入数字
while(r < q[i].r) add(++r);//加入数字
while(r > q[i].r) remove(r--);//移出数字
ans[q[i].id] = nowAns;
}
for(int i = 0;i < m;i++)
System.out.println(ans[i]);
}
}remove和add函数分别根据题目要求进行修改。看两道例题Powerful array、XOR and Favorite Number
腾讯云开发者
