【蓝桥备赛】wzy的数组Ⅱ——简单莫队问题
题目链接
wzy的数组Ⅱ
个人思路
本题需要统计区间范围内 数值为 x 在区间出现次数也为 x 的数的个数。区间询问 + 多次询问,我们选择 莫队。
将多次询问按照区间边界进行排序,每一次区间的移动,先去判断当前区间指针所指向的数是否符合题目条件,然后对该数的数量进行对应的增减操作,操作完之后,仍需判断当前数是否符合题目条件,因为数量发生了变化。
参考代码
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;/*
https://www.lanqiao.cn/problems/3247/learning/
*/int n, m, maxn, arr[N], cnt[N], sumn = 0, ans[N];class Query
{
public:int id, l, r;int operator<(const Query &x) const{if (l / maxn != x.l / maxn)return l < x.l;return (l / maxn) & 1 ? r < x.r : r > x.r;}
} q[N];void add(int i)
{if (cnt[arr[i]] == arr[i])sumn--;cnt[arr[i]]++;if (cnt[arr[i]] == arr[i])sumn++;
}void del(int i)
{if (cnt[arr[i]] == arr[i])sumn--;cnt[arr[i]]--;if (cnt[arr[i]] == arr[i])sumn++;
}int main()
{cin >> n >> m;maxn = sqrt(n);for (int i = 1; i <= n; ++i)cin >> arr[i];for (int i = 0; i < m; ++i){q[i].id = i;cin >> q[i].l >> q[i].r;}sort(q, q + m);int l = 1, r = 0;for (int i = 0; i < m; ++i){while (l > q[i].l){add(--l);}while (r < q[i].r){add(++r);}while (l < q[i].l){del(l++);}while (r > q[i].r){del(r--);}ans[q[i].id] = sumn;}for (int i = 0; i < m; ++i){cout << ans[i] << "\n";}return 0;
}
Java
import java.util.Arrays;
import java.util.Scanner;public class Main {static class Query implements Comparable<Query> {public int id, l, r;@Overridepublic int compareTo(Query x) {if (l / maxn != x.l / maxn)return Integer.compare(l, x.l);return (l / maxn) % 2 == 1 ? Integer.compare(r, x.r) : Integer.compare(x.r, r);}}static int n, m, maxn, sumn = 0;static int[] arr, cnt, ans;static Query[] q;static void add(int i) {if (cnt[arr[i]] == arr[i])sumn--;cnt[arr[i]]++;if (cnt[arr[i]] == arr[i])sumn++;}static void del(int i) {if (cnt[arr[i]] == arr[i])sumn--;cnt[arr[i]]--;if (cnt[arr[i]] == arr[i])sumn++;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();maxn = (int) Math.sqrt(n);arr = new int[n + 1];cnt = new int[n + 1];ans = new int[m];q = new Query[m];for (int i = 1; i <= n; ++i)arr[i] = scanner.nextInt();for (int i = 0; i < m; ++i) {q[i] = new Query();q[i].id = i;q[i].l = scanner.nextInt();q[i].r = scanner.nextInt();}Arrays.sort(q, 0, m);int l = 1, r = 0;for (int i = 0; i < m; ++i) {while (l > q[i].l) {add(--l);}while (r < q[i].r) {add(++r);}while (l < q[i].l) {del(l++);}while (r > q[i].r) {del(r--);}ans[q[i].id] = sumn;}for (int i = 0; i < m; ++i) {System.out.println(ans[i]);}}
}
由于还处于初学莫队,找了几个简单的莫队类型题目练练手,近期类似问题做了好几个,有兴趣的可以去我的蓝桥专栏下面看看。
相关文章:
【蓝桥备赛】wzy的数组Ⅱ——简单莫队问题
题目链接 wzy的数组Ⅱ 个人思路 本题需要统计区间范围内 数值为 x 在区间出现次数也为 x 的数的个数。区间询问 多次询问,我们选择 莫队。 将多次询问按照区间边界进行排序,每一次区间的移动,先去判断当前区间指针所指向的数是否符合题目…...
学习Qt笔记
前言: 学习笔记的内容来自B站up主阿西拜编程 《Qt6 C开发指南 》2023(上册,完整版)_哔哩哔哩_bilibili《Qt6 C开发指南 》2023(上册,完整版)共计84条视频,包括:00书籍介…...
pymssql 报错误解决办法:20002, severity 9
错误 解决办法 python3.6,安装pymssql低版本(pymssql-2.1.5-cp36-cp36m-win32.whl)...
Web缓存代理
目录 一.Web缓存代理 配置Nginx 缓存代理: 修改web服务器的配置文件: 修改192.168.233.10代理服务器的配置文件: 访问页面看看: 对于一些实时性要求非常高的页面或数据来说,就不应该去设置缓存,下面来…...
Rust-模式解构
match 首先,我们看看使用match的最简单的示例: exhaustive 有些时候我们不想把每种情况一一列出,可以用一个下划线来表达“除了列出来的那些之外的其他情况”: 下划线 下划线还能用在模式匹配的各种地方,用来表示…...
C#基于ScottPlot进行可视化
前言 上一篇文章跟大家分享了用NumSharp实现简单的线性回归,但是没有进行可视化,可能对拟合的过程没有直观的感受,因此今天跟大家介绍一下使用C#基于Scottplot进行可视化,当然Python的代码,我也会同步进行可视化。 P…...
基于JAVA+ssm开发的在线报名系统设计与实现【附源码】
基于JAVAssm开发的在线报名系统设计与实现【附源码】 🍅 作者主页 央顺技术团队 🍅 欢迎点赞 👍 收藏 ⭐留言 📝 🍅 文末获取源码联系方式 📝 🍅 查看下方微信号获取联系方式 承接各种定制系统 …...
蓝桥——第 3 场 小白入门赛(A-D)
文章目录 一、题目A.召唤神坤基本思路:代码 B.聪明的交换策略基本思路:代码 C.怪兽突击基本思路:代码 D.蓝桥快打基本思路代码 一、题目 A.召唤神坤 基本思路: 贪心, 使结果最大,希望两边w[i],w[k]是较大…...
Java项目:06 Springboot的进销存管理系统
作者主页:舒克日记 简介:Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 进销存管理系统 介绍 进销存系统是为了对企业生产经营中进货、出货、批发销售、付款等全程进行(从接获订单合同开 始,进入物料采购、入…...
数据结构与算法之美学习笔记:47 | 向量空间:如何实现一个简单的音乐推荐系统?
这里写自定义目录标题 前言算法解析总结引申 前言 本节课程思维导图: 很多人都喜爱听歌,以前我们用 MP3 听歌,现在直接通过音乐 App 在线就能听歌。而且,各种音乐 App 的功能越来越强大,不仅可以自己选歌听࿰…...
5《Linux》
文章目录 查看端口号查看进程号查看IP查看与某台机器连接情况 Linux查看日志的命令?head [-n 行数参数】tail [-n 行数参数】cat [-n 行号展示】tac [-n 行号展示】 Linux操作文本-三剑客grep-擅长过滤正则过滤sed-擅长取行awk-擅长取列 Linux性能监控的命令&#x…...
go-carbon v2.3.5 发布,轻量级、语义化、对开发者友好的 golang 时间处理库
carbon 是一个轻量级、语义化、对开发者友好的 golang 时间处理库,支持链式调用。 目前已被 awesome-go 收录,如果您觉得不错,请给个 star 吧 github.com/golang-module/carbon gitee.com/golang-module/carbon 安装使用 Golang 版本大于…...
VQ-VAE(Neural Discrete Representation Learning)论文解读及实现
pytorch 实现git地址 论文地址:Neural Discrete Representation Learning 1 论文核心知识点 encoder 将图片通过encoder得到图片点表征 如输入shape [32,3,32,32] 通过encoder后输出 [32,64,8,8] (其中64位输出维度) 量化码本 先随机构建一个码本,维度…...
OpenAI的ChatGPT:引领人工智能交流的未来
如果您在使用ChatGPT工具的过程中感到迷茫,别担心,我在这里提供帮助。无论您是初次接触ChatGPT plus,还是在注册、操作过程中遇到难题,我都将为您提供一对一的指导和支持。(qq:1371410959) 一、ChatGPT简介 OpenAI的ChatGPT是一…...
es集群安装及优化
es主节点 192.168.23.100 es节点 192.168.23.101 192.168.23.102 1.安装主节点 1.去官网下载es的yum包 官网下载地址 https://www.elastic.co/cn/downloads/elasticsearch 根据自己的需要下载对应的包 2.下载好之后把所有的包都传到从节点上,安装 [rootlocalho…...
【开源】基于JAVA+Vue+SpringBoot的医院门诊预约挂号系统
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 功能性需求2.1.1 数据中心模块2.1.2 科室医生档案模块2.1.3 预约挂号模块2.1.4 医院时政模块 2.2 可行性分析2.2.1 可靠性2.2.2 易用性2.2.3 维护性 三、数据库设计3.1 用户表3.2 科室档案表3.3 医生档案表3.4 医生放号…...
Java Swing 图书借阅系统 窗体项目 期末课程设计 窗体设计
视频教程: 【课程设计】图书借阅系统 功能描述: 图书管理系统有三个角色,系统管理员、图书管理员、借阅者; 系统管理员可以添加借阅用户; 图书管理员可以添加图书,操作图书借阅和归还; 借…...
2024.01.09.Apple_UI_BUG
我是软件行业的,虽然不是手机设计的,但是这个设计真的导致经常看信息不完整,要下拉的。 特别读取文本或者其他文件的时候,上面有个抬头就是看不到,烦,体验感很差...
K8S Nginx Ingress Controller client_max_body_size 上传文件大小限制
现象 k8s集群中,上传图片时,大于1M就会报错 413 Request Entity Too Large Nginx Ingress Controller 的版本是 0.29.0 解决方案 1. 修改configmap kubectl edit configmap nginx-configuration -n ingress-nginx在 ConfigMap 的 data 字段中设置参数…...
Untiy HTC Vive VRTK 开发记录
目录 一.概述 二.功能实现 1.模型抓取 1)基础抓取脚本 2)抓取物体在手柄上的角度 2.模型放置区域高亮并吸附 1)VRTK_SnapDropZone 2)VRTK_PolicyList 3)VRTK_SnapDropZone_UnityEvents 3.交互滑动条 4.交互旋…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
