算法自学__ 莫队
参考资料:
- https://zhuanlan.zhihu.com/p/115243708
普通莫队
算法思想
莫队算法基于分块的思想,可以解决离线的区间查询问题,时间复杂度为 O(nn)O(n\\sqrt n)O(nn) 。
一般来说,如果可以在 O(1)O(1)O(1) 内从 [l,r][l, r][l,r] 转移到 [l+1,r][l+1, r][l+1,r] 、[l,r−1][l, r-1][l,r−1] 、[l−1,r][l-1, r][l−1,r] 、[l,r+1][l, r+1][l,r+1] ,则可以考虑使用莫队。
莫队的基本步骤为:
- 先将
l
和r
分别初始化为1
和0
。 - 然后将查询区间按照左端点的块号升序排序;如果左端点块号相同,若块号为奇数,则将右端点按照升序排序,否则将右端点按照降序排序。
- 遍历排序后的查询区间,每次将
l
和r
暴力移动到区间的左右端点。
具体代码见例题。
例1 P1972 [SDOI2009] HH的项链
由于本题数据规模较大,故莫队只能拿部分分。但由于本题比较具有代表性,故选作莫队的例题。
题目大意
有一个长度为 nnn 序列,有 mmm 个询问,每次询问给出一个区间,问当前区间内有多少个不同的数。
思路
维护一个 cnt[]
数组,cnt[i]
表示当前区间中值为 i
的元素的个数;维护一个整数 sum
,表示当前区间中有多少不同的值。假设当前区间为 [l, r]
,如果我们从两端删除了一个数 i
,就令 cnt[i]--
,如果有 cnt[i] == 0
则说明该区间少了一个值,于是令 sum--
,代码如下:
// 消除位置 x 的元素的影响
void del(int x){cnt[a[x]]--;if(!cnt[a[x]]) sum--;
}
从区间两端加数的过程类似:
// 将位置 x 的元素考虑进来
void add(int x){if(!cnt[a[x]]) sum++;cnt[a[x]]++;
}
区间转移过程如下(先扩张,后收缩):
for(int i=1;i<=m;i++){while(l > node[i].l){add(--l);}while(r < node[i].r){add(++r);}while(l < node[i].l){del(l++);}while(r > node[i].r){del(r--);}ans[node[i].num] = sum;}
例2 P1494 [国家集训队] 小 Z 的袜子
题目大意
有一个长度为 nnn 序列,有 mmm 个询问,每次询问给出一个区间,从区间内随机取两个数,这两个数相等的概率是多少,输出最简分数。
思路
本题思路和上一题的类似,故直接给出代码。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;const int maxn = 5e4+5;int n, m, sq;
int a[maxn];
int l = 1, r = 0;
int cnt[maxn];
int sum = 0;
int ans[maxn];
int len[maxn];struct NODE{int num;int l, r;bool operator<(const NODE& x)const{int i1 = l/sq, j1 = x.l/sq;int i2 = r/sq, j2 = x.r/sq;if(i1 != j1){return i1 < j1;}else{if(i1&1){return i2 < j2;}else{return i2 > j2;}}}
};
NODE node[maxn];inline int getC(int x){return x*(x-1)/2;
} void add(int x){sum -= getC(cnt[a[x]]);cnt[a[x]]++;sum += getC(cnt[a[x]]);
}void del(int x){sum -= getC(cnt[a[x]]);cnt[a[x]]--;sum += getC(cnt[a[x]]);
}signed main(){cin>>n>>m;sq = sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){node[i].num = i;cin>>node[i].l>>node[i].r;}sort(node+1, node+1+m);for(int i=1;i<=m;i++){while(l>node[i].l){add(--l);}while(r<node[i].r){add(++r);}while(l<node[i].l){del(l++);}while(r>node[i].r){del(r--);}ans[node[i].num] = sum;len[node[i].num] = node[i].r-node[i].l+1;}for(int i=1;i<=m;i++){if(ans[i] == 0) cout<<"0/1";else{int tot = getC(len[i]);int g = __gcd(ans[i], tot);cout<<ans[i]/g<<'/'<<tot/g;}cout<<'\\n';} return 0;
}
例3 P8773 [蓝桥杯 2022 省 A] 选数异或
题目大意
给定一个长度为 nnn 的数列 A1,A2,⋯,AnA_{1}, A_{2}, \\cdots, A_{n}A1,A2,⋯,An 和一个非负整数 xxx, 给定 mmm 次查询, 每次询问能否从某个区间 [l,r][l, r][l,r] 中选择两个数使得他们的异或等于 xxx 。
思路
首先,若 a^b = x
,则有 a^x = b
。此时,问题转化成了:对区间内的每个元素 a[i]
,区间内是否存在值为 a[i]^x
的其他元素。
定义 cnt[i]
表示当前区间内值为 i
的元素的个数,定义 sum
表示当前区间异或值为 x
的元素对数。相关代码如下:
void add(int pos){cnt[a[pos]]++;sum += cnt[a[pos]^x];
}void del(int pos){cnt[a[pos]]--;sum -= cnt[a[pos]^x];
}