【模板】莫队算法

题目

洛谷P2709小B的询问

题解

莫队算法要求询问可以离线,并且要求被询问的区间信息便于从邻近区间转移。它是一种优化的暴力,通过将询问进行特殊的排序(方法有很多种),使得相似的询问排在一起,可以批量处理。被询问区间的排序方式:需要用到分块思想(将一段序列分成几段),所有被询问区间的左端点所在的分块的编号递增(即被询问区间的左端点大体呈递增趋势),每个分块内的区间右端点单调,且相邻分块的单调性相反(即被询问区间的右端点大体呈波浪形)。分块大小和排序方式的原因玄学,无法理论上求最优方式,只能测试。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月2日 下午10:52

【小白解析】
此题过于玄学,故只作大概分析,可能存在不准确的部分,请见谅。
从主函数入手。第一行(36行)是常规的快速读取,随后block长度的计算方法直接开幕雷击;依照博主说法,此为试验结果,故不做阐述(鄙人也做不出)。
37行读取每一个a后,顺便将1到n每一个数字分块:具体做法为当前数字编号(i-1)除以块长度(block)加1(确保block的编号从1开始)。
38行读取每一个问题。注意q[i].id实际上就是存储i的值,为了后续的再排序问题操作(见第48行)。
39行涉及所谓的“特殊排序方式”。排序方法cmp1见第16行,其具体思路为:

  1. 判断两个问题左端点所属的块是否是同一个。如果是,belong[x.l]^belong[y.l]==0(因为每一位都相同,异或操作使每一位为0),否则为1。
  2. 若为1,将问题数组q按左端点由小到大的顺序排序(belong[x.l]<belong[y.l])。
  3. 若为0,再判断块的编号的奇偶性(belong[x.l]&1,此处x.l和y.l作下标作用相同)。若为奇数,(1,3,5,……),则右端点需要按要求递减,故返回x.r>y.r;反之为偶数时(0,2,4,……),右端点递增,返回x.r<y.r。

随后到达40行开始的考察循环。此处l和r表示的实际意义是“区间[l,r]内的∑c^2”,因此分别对l和r进行考察:

  • 对l:
  • 若l在需要考察的q[i].l右侧,需要向左扩张l,故添加a[–l]直至l==q[i].l。用–l而非l–是因为此时的l已添加过,不需要再考虑,故先减一再添加下一位。
  • 若l在需要考察的q[i].l左侧,需要向右扩张l。此时用l++而非++l是因为此时的l在区间外,必须排除,故先删除l后添加。
  • 对r:
  • 基本同理,对调l和r的性质即可推出。

39行初始化l为1,r为0为极端情况,为了保证第一组数据一定能被执行while()操作。
add()和del()方法的实现其实很简单:先删去当前数字x出现次数sum[x]的平方,后增加/减少sum[x]的数量,再加上更新后x出现次数的平方,即可达成目的。
一次循环完结后,l==q[i].l,r==q[i].r,故此时l,r所达成的ans即是q[i]所需要的答案,故将其赋值给q[i].ans。
最后第48行,根据q[i].id的排序还原问题最初的提出顺序,随后打印答案。
*我怕了。