莫队学习笔记

作者: 来源: 博客园 2023-07-01 21:39:22

 引入问题

给出一个长度为 \(n\) 的数组 \(A\),接下来 \(q\) 次询问,每次询问求 \([l,r]\) 中有多少组 \((i,j,k)\) 使得 \(a_i=a_j=a_k(i


【资料图】

保证 \(1\leq n\leq 10^5,1\leq A_i\leq n(1\leq i\leq n)\)。

莫队的基础思想——区间转移

简单分析问题,貌似并没有可加性,所以分块和线段树肯定寄了。

但是本题中相邻区间转移是 \(O(1)\):

对于增加元素,设原有此元素 \(n\) 个,则增加三元组 \(\dfrac 1 2n(n-1)\) 个。对于删除元素,设减去该元素后有此元素 \(n\) 个,则减少三元组 \(\dfrac 1 2n(n-1)\) 个。

莫队算法是一种解决此类问题的离线算法,它基于以下思想:

我们不难考虑到一个暴力代码,它的框架如下:

void del(LL x){cnt[a[x]]--;sum-=cnt[a[x]]*(cnt[a[x]]-1)/2;}void ins(LL x){sum+=cnt[a[x]]*(cnt[a[x]]-1)/2;cnt[a[x]]++;}LL l=1,r=0,sl,sr;for(int i=1;i<=q;i++){sl=b[i].l,sr=b[i].r;while(l

该代码中出现的函数,ins(x)表示算上 \(x\) 这一项的贡献,del(x)表示删除 \(x\) 这一项的贡献。

不难看出,这份代码本质上是对于询问区间的移动。

如果我们保证区间移动次数较少的话,时间复杂度也会比较优秀。

我们有什么思路呢?

时间复杂度优秀的秘密——分块

我们取 \(B=\sqrt n\) 为块长进行分块,然后,按照左边界所在的块的编号给询问区间排序,同一个块则用右边界排序。

不难得到如下代码:

bool cmp(node x,node y){if(x.l/B==y.l/B)return x.r

我们来分析一下时间复杂度:

左边界块内移动,每次时间复杂度 \(O(\sqrt n)\),有 \(q\) 次,时间复杂度为 \(O(q\sqrt n)\)。左边界越块移动,每次翻过一个块的时间复杂度是 \(O(\sqrt n)\),有 \(\sqrt n\) 次,时间复杂度为 \(O(n)\)。对于每个左边界的块,右边界的移动整体来看都是 \(O(n)\) 的,有 \(\sqrt n\) 个块,时间复杂度为 \(O(n\sqrt n)\)。

因此,莫队的整体时间复杂度是 \(O(n\sqrt n)\)。

玄学优化——奇偶性优化

对于编号为奇数的块,我们用右边界从小到大排序,对于编号为偶数的块,我们用右边界从大到小排序。

这样会快一点,因为不加优化之前来到新的块右端点需要先回溯至这个块里最小的右端点。

但是加了这个优化,有时我们可以从原先的最右边从右往左依次处理新的块的询问,所以会快一点。

代码实现
#include#define LL long longusing namespace std;const LL N=2e5+5;struct node{LL l,r,id;}b[N];LL n,q,B,a[N],cnt[N],ans[N],sum;bool cmp(node x,node y){if(x.l/B==y.l/B){if((x.l/B)&1)return x.ry.r;}return x.l/B
 

相关文章
最近更新
  • 莫队学习笔记

    莫队学习笔记

    2023-07-01

  • AITO 问界销服联合工作组成立,华为与赛力斯跨界合作再深化-全球时讯

    AITO 问界销服联合工作组成立,华为与赛力斯跨界合作再深化-全球时讯

    2023-07-01

  • 世界热议:国青控股集团与马里代表团达成多项重要合作

    世界热议:国青控股集团与马里代表团达成多项重要合作

    2023-07-01

  • 环球报道:前腰和前锋有什么区别(前腰)

    环球报道:前腰和前锋有什么区别(前腰)

    2023-07-01

  • 唯购微商城下载安装_唯购 今日最新

    唯购微商城下载安装_唯购 今日最新

    2023-07-01

  • 遇到紧急情况避险时_遇紧急情况避险时坚持什么原则

    遇到紧急情况避险时_遇紧急情况避险时坚持什么原则

    2023-07-01

  • 台上话筒故障,浙江12岁男孩后台完美救场!一开嗓惊艳众人-世界播报

    台上话筒故障,浙江12岁男孩后台完美救场!一开嗓惊艳众人-世界播报

    2023-07-01

  • 世界今热点:首届长三角一体化发展司法论坛在华政举行 推动司法机关与高校优势互补

    世界今热点:首届长三角一体化发展司法论坛在华政举行 推动司法机关与高校优势互补

    2023-07-01

  • 数字媒体技术就业前景和待遇(数字媒体技术就业前景)

    数字媒体技术就业前景和待遇(数字媒体技术就业前景)

    2023-07-01

  • 火锅蘸酱牌子_火锅蘸酱

    火锅蘸酱牌子_火锅蘸酱

    2023-07-01

  • 知情人士透露河南“书法家”杀害女子案件细节:民警拉网排查发现嫌犯已自缢身亡

    知情人士透露河南“书法家”杀害女子案件细节:民警拉网排查发现嫌犯已自缢身亡

    2023-07-01

  • 天天即时:惠普打印机e3故障码_惠普打印机e3故障

    天天即时:惠普打印机e3故障码_惠普打印机e3故障

    2023-07-01

  • 环球微速讯:网上一对一授课哪个软件好_网上一对一授课

    环球微速讯:网上一对一授课哪个软件好_网上一对一授课

    2023-07-01

  • 神州行畅听卡(关于神州行畅听卡介绍)

    神州行畅听卡(关于神州行畅听卡介绍)

    2023-07-01

  • 【新要闻】神界传说:虽然被关押起来,但是大家都很开心,唐三也开始学做饭

    【新要闻】神界传说:虽然被关押起来,但是大家都很开心,唐三也开始学做饭

    2023-07-01

  • 世界今日报丨形容白色的古诗有哪些
6.描写“白色”的句子有哪些

    世界今日报丨形容白色的古诗有哪些 6.描写“白色”的句子有哪些

    2023-07-01

  • 中央委员丁学东,履新职

    中央委员丁学东,履新职

    2023-07-01

  • “量身定做式”职称晋升危害大!老师们更愿意按教学成绩考核 今日观点

    “量身定做式”职称晋升危害大!老师们更愿意按教学成绩考核 今日观点

    2023-07-01

  • 蔚来汽车 6 月交付 10707 辆,环比增长 74%-当前聚焦

    蔚来汽车 6 月交付 10707 辆,环比增长 74%-当前聚焦

    2023-07-01

  • 煌上煌(002695.SZ)拟推2023年员工持股计划 募资总额不超2424.46万元 天天最新

    煌上煌(002695.SZ)拟推2023年员工持股计划 募资总额不超2424.46万元 天天最新

    2023-07-01

  • 环球微头条丨肌营养不良的最新治疗希望御圣本草养元汤

    环球微头条丨肌营养不良的最新治疗希望御圣本草养元汤

    2023-07-01

  • 淘宝开店卖虚拟产品需要交钱吗?有哪些规则?

    淘宝开店卖虚拟产品需要交钱吗?有哪些规则?

    2023-07-01

  • 炉石卡德加皮肤回归2021_炉石传说卡德加皮肤怎么领取2021相关介绍简介

    炉石卡德加皮肤回归2021_炉石传说卡德加皮肤怎么领取2021相关介绍简介

    2023-07-01

  • 【天天时快讯】泡茶水温是多少合适_泡茶水温

    【天天时快讯】泡茶水温是多少合适_泡茶水温

    2023-07-01

  • 环球热讯:美国今年已发生186起儿童意外枪击事件 5、6月数字创新高

    环球热讯:美国今年已发生186起儿童意外枪击事件 5、6月数字创新高

    2023-07-01

  • 焦点速读:陵城区高温橙色预警

    焦点速读:陵城区高温橙色预警

    2023-07-01

  • 三水区发布暴雨黄色预警 环球视点

    三水区发布暴雨黄色预警 环球视点

    2023-07-01

  • 深蓝汽车推动电动平权、智能平权 加速实现全场景智慧出行

    深蓝汽车推动电动平权、智能平权 加速实现全场景智慧出行

    2023-07-01

  • 切尔西功勋队长离队,ZAP弃国米重返西甲,蓝桥永远感念他的贡献

    切尔西功勋队长离队,ZAP弃国米重返西甲,蓝桥永远感念他的贡献

    2023-07-01

  • 环球热议:汉仪股份联合798文化科技主办白洞甲骨文艺术展正式开幕

    环球热议:汉仪股份联合798文化科技主办白洞甲骨文艺术展正式开幕

    2023-07-01