AcWing 2492：HH的项链 ← 基础莫队算法

【题目来源】https://www.acwing.com/problem/content/2494/https://www.luogu.com.cn/problem/P1972【题目描述】HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运所以每次散步完后他都会随意取出一段贝壳思考它们所表达的含义。HH 不断地收集新的贝壳因此他的项链变得越来越长。有一天他突然提出了一个问题某一段贝壳中包含了多少种不同的贝壳这个问题很难回答因为项链实在是太长了。于是他只好求助睿智的你来解决这个问题。【输入格式】第一行一个整数 N表示项链的长度。第二行N 个整数表示依次表示项链中贝壳的编号编号为 0 到 1000000 之间的整数。第三行一个整数 M表示 HH 询问的个数。接下来 M 行每行两个整数L 和 R表示询问的区间。【输出格式】M 行每行一个整数依次表示询问对应的答案。【数据范围】1≤N≤50000,1≤M≤2×10^5,1≤L≤R≤N【输入样例】61 2 3 4 3 531 23 52 6【输出样例】224【算法分析】● 基础莫队算法是一种离线算法通常用于“不修改、只查询”的一类区间问题。莫队算法的时间复杂度为。● 莫队算法离线暴力分块。“在线”是交互式的一问一答。特别的如果前面的答案用于后面的提问称为“强制在线”。“离线”是非交互的一次性读取所有问题一起回答。● 莫队算法的精髓在于奇偶性排序。也就是依据左端点 L 位于奇数块还是偶数块决定右端点 R从小到大排序还是从大到小排序。1首先利用分块算法将给定的 n 个数分成 sqrt(n) 个块2然后将多个询问的左端点L按块从小到大排序。若 L 位于奇数块则对右端点R 从小到大排序。若 L 位于偶数块则对右端点R 从大到小排序。反之亦可。示意图如下所示● 莫队算法中定义的数组cnt[x]表示数字 x 出现的次数。莫队算法不同题目的代码区别主要在于add()函数和del()函数其他部分代码基本一致。● 竞赛标准写法先扩张再收缩保证不会在空区间删除元素。参见https://blog.csdn.net/hnjzsyjyj/article/details/163143122while(riq[i].ri) add(ri); while(leq[i].le) add(--le); while(riq[i].ri) del(ri--); while(leq[i].le) del(le);● “分块”算法的基本要素特别的参考https://blog.csdn.net/hnjzsyjyj/article/details/138955263可知“分块”算法的一些技术细节。如下所述1块的大小用 block 表示。通常令blocksqrt(n)。其中n 为元素个数。2块的数量用 cnt 表示。计算块的数量的代码如下int blocksqrt(n); int cntn/block; if(n % block) cnt;3定义pos[i]为第 i 个元素所在的块。若下标从 1 开始则有pos[i](i-1)/block1。其中blocksqrt(n)。若下标从 0 开始则有pos[i]i/block。其中blocksqrt(n)。4块的左边界 le[]及右边界 ri[]。若用 le[i] 和 ri[i] 分别表示块 i 的第一个和最后一个元素的位置。若下标从 1开始则有le[1]1, ri[1]block; le[2]block1, ri[2]2*block; …… le[i](i-1)*block1, ri[i]i*block; ……若下标从 0开始则有le[0]0, ri[0]block-1; le[1]block, ri[1]2*block-1; …… le[i]i*block, ri[i](i1)*block-1; ……综上“分块”算法build()函数的构建细节如下。1下标从 0 开始build() 函数的构建如下。void build(int n) { int blocksqrt(n); int cntn/block; if(n%block) cnt; for(int i0; icnt; i) { le[i]i*block; ri[i](i1)*block-1; } ri[cnt-1]n-1; for(int i0; in; i) pos[i]i/block; }2下标从 1 开始build() 函数的构建如下。void build(int n) { int blocksqrt(n); int cntn/block; if(n%block) cnt; for(int i1; icnt; i) { le[i](i-1)*block1; ri[i]i*block; } ri[cnt]n; for(int i1; in; i) pos[i](i-1)/block1; }特别注意针对不同的问题利用“分块”算法进行分析时下图将具有极高的应用价值。其对整块及碎块的处理一目了然。分块算法示例详见洛谷P3372线段树 1 →https://blog.csdn.net/hnjzsyjyj/article/details/138863063洛谷 P3203弹飞绵羊 →https://blog.csdn.net/hnjzsyjyj/article/details/138903837HDU 5057Argestes and Sequence →https://blog.csdn.net/hnjzsyjyj/article/details/138926594【算法代码】注意本代码AcWing 2492 能过但洛谷 P1972 数据加强了导致用莫队算法求解时部分样例会超时TLE故建议用树状数组或线段树来做洛谷 P1972 。本题代码与“洛谷 P2709[模板] 莫队 / 小 B 的询问 → https://blog.csdn.net/hnjzsyjyj/article/details/163114366”的代码主要在于add()函数和del()函数不同其他部分代码基本一致。如下所示。#include bits/stdc.h using namespace std; typedef long long LL; const int N1e65; LL a[N],cnt[N],ans[N]; int block,n,m,k; LL cur; struct Node { int le,ri,idx; } q[N]; bool cmp(Node a,Node b) { if(a.le/block!b.le/block) { return a.leb.le; } return a.rib.ri; } void add(int x) { int vala[x]; if(cnt[val]0) cur; cnt[val]; } void del(int x) { int vala[x]; cnt[val]--; if(cnt[val]0) cur--; } int main() { ios::sync_with_stdio(0); cin.tie(0); cinn; for(int i1; in; i) cina[i]; cinm; blocksqrt(n); for(int i0; im; i) { cinq[i].leq[i].ri; q[i].idxi; } sort(q,qm,cmp); int le1,ri0; for(int i0; im; i) { while(riq[i].ri) add(ri); while(leq[i].le) add(--le); while(riq[i].ri) del(ri--); while(leq[i].le) del(le); ans[q[i].idx]cur; } for(int i0; im; i) { coutans[i]\n; } return 0; } /* in: 6 1 2 3 4 3 5 3 1 2 3 5 2 6 out: 2 2 4 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/163114366https://www.cnblogs.com/wner/p/18007108https://www.acwing.com/solution/content/23426/https://blog.sengxian.com/algorithms/mo-s-algorithmhttps://blog.csdn.net/m0_63737271/article/details/125786194https://blog.csdn.net/GROZAX/article/details/130069889https://blog.csdn.net/weixin_75161465/article/details/137195888