【算法】莫队

这篇博客起源于本人把一道 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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/144752.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

nginx 多层代理 + k8s ingress 后端服务获取客户真实ip 配置

1.nginx http 七层代理 修改命令空间&#xff1a; namespace: nginx-ingress : configmap&#xff1a;nginx-configuration kubectl get cm nginx-configuration -n ingress-nginx -o yaml添加如上配置 compute-full-forwarded-for: “true” forwarded-for-header: X-Forwa…

点击、拖拉拽,BI系统让业务掌握数据分析主动权

在今天的商业环境中&#xff0c;数据分析已经成为企业获取竞争优势的关键因素之一。然而&#xff0c;许多企业在面对复杂的数据分析工具时&#xff0c;却常常感到困扰。这些工具往往需要专业的技术人员操作&#xff0c;而且界面复杂&#xff0c;难以理解和使用。对业务人员来说…

JDK17新特性

为什么要升级JDK17 JDK17带来了哪些变化 swtich语句增强 // jdk8switch int statusCode 0; String statusName ""; switch (statusCode) {case 1:statusName "开始";break;case 2:statusName "进行中";break;case 3:statusName "结束…

【ARMv8 SIMD和浮点指令编程】NEON 加载指令——如何将数据从内存搬到寄存器(LDxLDxR)?

将内存中的数据搬到 NEON 寄存器,有很多指令可以完成,熟悉这些指令是必须的。 1 LD1 (multiple structures) 将多个单元素结构加载到一个,两个,三个或四个寄存器上。该指令从内存中加载多个单元结构,并将结果写入一、二、三或四个 SIMD&FP 寄存器。 无偏移 一个寄存…

基于nodejs+vue办公OA公文发文件管理系统

论文的研究内容包括&#xff1a;公文分类、公文信息、待办提醒等方面进行了研究。系统以当前应用最为广泛的nodejs语言为基础&#xff0c;结合了目前应用最为广泛的嵌入式嵌入式平台&#xff0c;集成了B/S体系结构。数据库选择简便高效的MySQL&#xff0c;vue框架。在OA公文发文…

简单理解旁路电容和去耦电容

1、本文内容如有错误&#xff0c;欢迎交流指正。 2、本文仅作为本人学习笔记&#xff0c;部分内容来源于网络、书籍&#xff0c;如涉及侵权&#xff0c;请联系删除。 什么是旁路电容&#xff1f; 旁路电容的英文原文是Bypass capacitor&#xff0c;bypass就是绕过&#xff0c;避…

Spring修炼之路(2)依赖注入(DI)

一、概念 依赖注入&#xff08;Dependency Injection,DI&#xff09;。 测试pojo类 : Address.java 依赖 : 指Bean对象的创建依赖于容器 . Bean对象的依赖资源 . 注入 : 指Bean对象所依赖的资源 , 由容器来设置和装配 . 二、 注入方式 2.1构造器注入 我们在之前的案例已经…

系统集成|第十二章(笔记)

目录 第十二章 沟通管理12.1 沟通的基本概念12.2 主要过程12.2.1 规划沟通管理12.2.2 管理沟通12.2.3 控制沟通 12.3 常见问题 上篇&#xff1a;第十一章、项目人力资源管理 下篇&#xff1a;第十三章、干系人管理 第十二章 沟通管理 沟通管理在项目计划、执行、监控过程中具有…

echarts添加点击事件

实现效果&#xff1a;点击图表&#xff0c;弹出该数据下对应得详情 官方文档&#xff1a; 封装的图表组件中&#xff1a; 点击获取点击得对象&#xff0c;进而将需要的参数传给父组件&#xff0c;在父组件中再去请求接口获取更多信息 this.chart.on(click, (params)> {th…

C# 数组

C# 数组 数组简单数组多维数组锯齿数组Array类数组的接口枚举 数组 如果需要使用同一类型的多个对象&#xff0c;就可以使用集合和数组。C#用特殊的记号声明和使用数组。 简单数组 在声明数组时&#xff0c;应先定义数组中元素的类型&#xff0c;其后是一个空方括号和一个变…

Docker 自动化部署(保姆级教程)

Docker 自动化部署 1. jenkins 介绍1.1 参考链接&#xff1a;1.2 jenkins 概述1.3 jenkins部署项目的流程 2. jenkins 安装2.1 基于docker 镜像2.2 启动 jenkins 后端服务2.3 登录 jenkins 服务后端 3. jenkins自动化部署开始3.1 下载需要的插件3.2 创建任务3.2.1 描述3.2.2 配…

【图论C++】树的重心——教父POJ 3107(链式前向星的使用)

》》》算法竞赛 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在竞赛算法学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记&#xff1a;转载…

Neo4j-双向关系

概述 这是GraphAware中关于双向关系的解释。 网址链接Modelling Data in Neo4j: Bidirectional Relationships | GraphAware 定向关系 Neo4j中的关系必须有一个语义化的类型和方向。 没有方向关系是模棱两可的&#xff0c;上面A队打败B队&#xff0c;如果没有方向&#xff0c…

AOP 编程

目录 ​编辑一、AOP 编程 1、AOP 概念 2、AOP 编程的开发步骤 3、切面的名词解释 二、AOP 的底层实现原理 1、核心问题 2、动态代理类的创建 &#xff08;1&#xff09;JDK 的动态代理创建 &#xff08;2&#xff09;CGlib 的动态代理 &#xff08;3&#xff09;总结…

支持笔记本电脑直插直充,TOWE 65W智能快充PDU超级插座

电源插排在我们的生活中是必不可少的电器配件。今天&#xff0c;我们日常生活中所使用的电子设备越来越多&#xff0c;无论是手机、平板、笔记本电脑还是各种家用电器&#xff0c;都需要电源来驱动。虽然相对于其他电器来说&#xff0c;插排结构比较简单&#xff0c;但现代家庭…

设计模式5、原型模式 Prototype

解释说明&#xff1a;使用原型实例指定待创建对象的类型&#xff0c;并且通过复制这个原型阿里创建型的对象 UML 结构图&#xff1a; 抽象原型&#xff08;Prototype&#xff09;&#xff1a;规定了具体原型对象必须实现的clone()方法 具体原型&#xff08;ConcretePrototype&…

【我的创作纪念日】使用pix2pixgan实现barts2020数据集的处理(完整版本)

使用pix2pixgan &#xff08;pytorch)实现T1 -> T2的基本代码 使用 https://github.com/eriklindernoren/PyTorch-GAN/ 这里面的pix2pixgan代码进行实现。 进去之后我们需要重新处理数据集&#xff0c;并且源代码里面先训练的生成器&#xff0c;后训练鉴别器。 一般情况下…

计算机图像处理-均值滤波

均值滤波 线性滤波器的原始数据与滤波结果是一种算术运算&#xff0c;即用加减乘除等运算实现&#xff0c;如均值滤波器&#xff08;模板内像素灰度值的平均值&#xff09;、高斯滤波器&#xff08;高斯加权平均值&#xff09;等。由于线性滤波器是算术运算&#xff0c;有固定…

Android Jetpack Compose之确定重组范围并优化重组

1.概述 Compose的重组是智能的&#xff0c;Composable函数在进行重组时会尽可能的跳过不必要的重组&#xff0c;只对需要变化的UI进行重组。那Compose是如何认定UI需要变化呢&#xff1f;或者换句话说Compose是如何确定重组的范围呢。如果重组随意的发生&#xff0c;那么对UI的…

LabVIEW开发实时自动化多物镜云计算全玻片成像装置

LabVIEW开发实时自动化多物镜云计算全玻片成像装置 数字病理学领域正在迅速发展&#xff0c;这主要是由于计算机处理能力、数据传输速度、软件创新和云存储解决方案方面的技术进步。因此&#xff0c;病理科室不仅将数字成像用于图像存档等简单任务&#xff0c;还用于远程病理学…