这篇博客起源于本人把一道 p o w ( 2 , n ) pow(2,n) pow(2,n) 的问题考虑成求组合数前缀和的问题qwq,于是接触到了这个新算法来总结一下
参考自这篇文章,写得太好了
首先是一道模板题
题目意思是,给出一个数组a,再给出多个区间,问这些区间里分别有多少不一样的数字
焗个栗子:
比如给出的是这样一个数组,询问的两个区间是红色和绿色标注的区间
如果我们分别遍历每一个区间,复杂度就太高了,因此就有大佬提出这样一种算法——
首先定义双指针 l l l、 r r r,初始化为 l = 0 , r = − 1 l=0,r=-1 l=0,r=−1(表示此时区间内没有任何元素),然后用unorderd_map<int, int> map
存储当前区间内每个元素的个数
看我们要求的第一个区间 [ 0 , 5 ] [0,5] [0,5]
l l l 此时等于 0 0 0,和所求区间的左端点相同,因此无需移动
r r r 此时等于 − 1 -1 −1,在所求区间右端点的左侧,因此需要向右移
首先向右移一位变成 0 0 0,此时区间内添加了一个元素 5,因为map[5] = 0
,元素5不存在于原来的区间里,因此元素种类数cnt
加一,map[5] ++
然后 r r r 再右移一位变成 1,此时区间内添加了一个元素 7,因为map[7] = 0
,元素7不存在于原来的区间里,因此元素种类数cnt
加一,map[7] ++
依此类推,直到 r r r 右移到了 5,此时区间内添加了一个元素 7,但是添加前的map[7] = 1
,添加了当前的 7 并不会让区间内元素的个数增多,因此cnt
无需改变,map[7] ++
之后从红色区间挪到绿色区间的操作也是类似的
上文介绍了如何往区间内添加数,当然,删除一个数的操作也是类似的,只不过添加数时,我们要先看被添加的数有没有出现在原来的区间里,也就是map[x]
是否等于0,如果等于0说明不存在于原来的区间,区间内元素种类数cnt
才能加一,而删除数时,我们要先把当前数删除,也就是map[x]
减一,然后再判断当前区间里还有没有x,如果没有x也就是map[x] == 0
,那么区间内元素种类数cnt
减一
code
// 添加数
void add(int pos)
{if (!map[a[pos]]) cnt ++ ; // 在区间中新出现,总数要+1map[a[pos]] ++ ;
}// 删除数
void del(int pos)
{map[a[pos]] -- ;if (!map[a[pos]]) cnt -- ; // 在区间中不再出现,总数要-1
}int main()
{for (int i = 1; i <= q; ++i){// 输入询问区间的左右端点int ql, qr;cin >> ql >> qr;while (l < ql) del(l++); // 如左指针在查询区间左方,左指针向右移直到与查询区间左端点重合while (l > ql) add(--l); // 如左指针在查询区间左端点右方,左指针左移while (r < qr) add(++r); // 右指针在查询区间右端点左方,右指针右移while (r > qr) del(r--); // 否则左移cout << cnt;}
}
然后就 结束啦 qwq
才怪
还可以对这个算法继续优化
莫队算法优化的核心是分块和排序
把长度为 n n n 的序列分成 n \sqrt{n} n 个块,然后按照左端点所在的块排序,如果左端点在同一个块内,则按右端点排序
优化1
这种排序方法也可以接着优化:如果左端点在同一奇数块内,则按右端点从小到大排序,如果左端点在同一偶数块内,则按右端点从大到小排序,这样排序是为了减少右端点移动的次数进而提高效率)
优化2
听说开O2优化能产生奇妙反应,实在没办法了可以考虑考虑这个
#pragma GCC optimize(2)
优化3
某佬把上面的一长串代码简化成了下面这样
while(l < ql) cnt -= !--map[a[l++]];
while(l > ql) cnt += !map[a[--l]]++;
while(r < qr) cnt += !map[a[++r]]++;
while(r > qr) cnt -= !--map[a[r--]];
于是模板题的代码如下
#include <bits/stdc++.h>using namespace std;typedef pair<pair<int, int>, int> PPI;int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;cin >> n;int size = sqrt(n);int bnum = ceil((double)n / size); // 把序列分成了多少块vector<int> belong(1e6 + 10);for (int i = 1; i <= bnum; i ++ )for (int j = (i - 1) * size + 1; j <= i * size; j ++ ){belong[j] = i; // 标记每个元素属于哪个块}vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];int m;cin >> m;vector<PPI> q(m);for (int i = 0; i < m; i ++ ){cin >> q[i].first.first >> q[i].first.second;q[i].second = i;}function<bool(PPI a, PPI b)> cmp = [&](PPI a, PPI b){// return (belong[a.first.first] ^ belong[b.first.first]) ? belong[a.first.first] < belong[b.first.first] : ((belong[a.first.first] & 1) ? a.first.second < b.first.second : a.first.second > b.first.second);if (belong[a.first.first] != belong[b.first.first]) return belong[a.first.first] < belong[b.first.first];else{if (belong[a.first.first] % 2 == 1) return belong[a.first.second] < belong[b.first.second];else return belong[a.first.second] > belong[b.first.second];}};sort(q.begin(), q.end(), cmp);int l = 1, r = 0, cnt = 0;unordered_map<int, int> map;vector<int> ans(m);for (int i = 0; i < m; i ++ ){int ql = q[i].first.first, qr = q[i].first.second;while(l < ql) cnt -= !--map[a[l ++ ]];while(l > ql) cnt += !map[a[-- l]] ++;while(r < qr) cnt += !map[a[++ r]] ++;while(r > qr) cnt -= !--map[a[r -- ]];ans[q[i].second] = cnt;}for (int i = 0; i < m; i ++ ) cout << ans[i] << '\n';
}
剩下的之后更新~~qwq