莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。
有n个数字,给出k,以及m个查询。每次查询的格式是L,R,求L~R(左闭右闭)这个区间内数字的出现次数刚好是k的数字种数。
5 2 3
1 2 3 2 2
1 2
2 4
1 5
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),这就是莫队算法,具体的证明过程可以看网上的文章
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);
}
}
莫队的精髓就在于,离线得到了一堆需要处理的区间后,合理的安排这些区间的计算次序以得到一个较优的复杂度
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