莫队算法
有一个序列,且有一些区间询问,便可以考虑用神奇的莫队算法!
实现
莫队是一种离线算法,用到了分块的思想,将序列分块,设每个块的长度为。在输入所有询问之后,按
二元组从小到大排序,之后按顺序暴力移动左右端点并统计答案。
时间复杂度
设序列的长度为,询问个数为
,从
扩展到
的时间复杂度为
,于是从
转移到
的时间为
对于每一个块中的所有询问,最多使
移动
,每个询问最多使
移动
,一共有
,相邻两个块转移的时间复杂度为
,所以总时间复杂度为
,当
同阶时,使
,总时间复杂度即为
模板
1 2 3 4 5 6 7 8 |
bool quescomp(T x, T y) { if (knum[x.l] == knum[y.l]) { return x.r < y.r; } return knum[x.l] < knum[y.l]; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
int knumber = (int)sqrt(n); for (int i = 1; i <= n; i++) { knum[i] = (i - 1) / knumber + 1; } std::sort(ques + 1, ques + T + 1, quescomp); for (int i = 1, l = 1, r = 0; i <= Q; i++) { for (; l < ques[i].l; l++) { update(l, -1); } for (; l > ques[i].l; l--) { update(l - 1, 1); } for (; r < ques[i].r; r++) { update(r + 1, 1); } for (; r > ques[i].r; r--) { update(r, -1); } //calc ans } |
%%%
膜拜FKC大佬