当前位置: 首页 > news >正文

【蓝桥备赛】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 的数的个数。区间询问 多次询问&#xff0c;我们选择 莫队。 将多次询问按照区间边界进行排序&#xff0c;每一次区间的移动&#xff0c;先去判断当前区间指针所指向的数是否符合题目…...

学习Qt笔记

前言&#xff1a; 学习笔记的内容来自B站up主阿西拜编程 《Qt6 C开发指南 》2023&#xff08;上册&#xff0c;完整版&#xff09;_哔哩哔哩_bilibili《Qt6 C开发指南 》2023&#xff08;上册&#xff0c;完整版&#xff09;共计84条视频&#xff0c;包括&#xff1a;00书籍介…...

pymssql 报错误解决办法:20002, severity 9

错误 解决办法 python3.6&#xff0c;安装pymssql低版本&#xff08;pymssql-2.1.5-cp36-cp36m-win32.whl&#xff09;...

Web缓存代理

目录 一.Web缓存代理 配置Nginx 缓存代理&#xff1a; 修改web服务器的配置文件&#xff1a; 修改192.168.233.10代理服务器的配置文件&#xff1a; 访问页面看看&#xff1a; 对于一些实时性要求非常高的页面或数据来说&#xff0c;就不应该去设置缓存&#xff0c;下面来…...

Rust-模式解构

match 首先&#xff0c;我们看看使用match的最简单的示例&#xff1a; exhaustive 有些时候我们不想把每种情况一一列出&#xff0c;可以用一个下划线来表达“除了列出来的那些之外的其他情况”&#xff1a; 下划线 下划线还能用在模式匹配的各种地方&#xff0c;用来表示…...

C#基于ScottPlot进行可视化

前言 上一篇文章跟大家分享了用NumSharp实现简单的线性回归&#xff0c;但是没有进行可视化&#xff0c;可能对拟合的过程没有直观的感受&#xff0c;因此今天跟大家介绍一下使用C#基于Scottplot进行可视化&#xff0c;当然Python的代码&#xff0c;我也会同步进行可视化。 P…...

基于JAVA+ssm开发的在线报名系统设计与实现【附源码】

基于JAVAssm开发的在线报名系统设计与实现【附源码】 &#x1f345; 作者主页 央顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承接各种定制系统 …...

蓝桥——第 3 场 小白入门赛(A-D)

文章目录 一、题目A.召唤神坤基本思路&#xff1a;代码 B.聪明的交换策略基本思路&#xff1a;代码 C.怪兽突击基本思路&#xff1a;代码 D.蓝桥快打基本思路代码 一、题目 A.召唤神坤 基本思路&#xff1a; 贪心&#xff0c; 使结果最大&#xff0c;希望两边w[i],w[k]是较大…...

Java项目:06 Springboot的进销存管理系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 进销存管理系统 介绍 进销存系统是为了对企业生产经营中进货、出货、批发销售、付款等全程进行&#xff08;从接获订单合同开 始&#xff0c;进入物料采购、入…...

数据结构与算法之美学习笔记:47 | 向量空间:如何实现一个简单的音乐推荐系统?

这里写自定义目录标题 前言算法解析总结引申 前言 本节课程思维导图&#xff1a; 很多人都喜爱听歌&#xff0c;以前我们用 MP3 听歌&#xff0c;现在直接通过音乐 App 在线就能听歌。而且&#xff0c;各种音乐 App 的功能越来越强大&#xff0c;不仅可以自己选歌听&#xff0…...

5《Linux》

文章目录 查看端口号查看进程号查看IP查看与某台机器连接情况 Linux查看日志的命令&#xff1f;head [-n 行数参数】tail [-n 行数参数】cat [-n 行号展示】tac [-n 行号展示】 Linux操作文本-三剑客grep-擅长过滤正则过滤sed-擅长取行awk-擅长取列 Linux性能监控的命令&#x…...

go-carbon v2.3.5 发布,轻量级、语义化、对开发者友好的 golang 时间处理库

carbon 是一个轻量级、语义化、对开发者友好的 golang 时间处理库&#xff0c;支持链式调用。 目前已被 awesome-go 收录&#xff0c;如果您觉得不错&#xff0c;请给个 star 吧 github.com/golang-module/carbon gitee.com/golang-module/carbon 安装使用 Golang 版本大于…...

VQ-VAE(Neural Discrete Representation Learning)论文解读及实现

pytorch 实现git地址 论文地址&#xff1a;Neural Discrete Representation Learning 1 论文核心知识点 encoder 将图片通过encoder得到图片点表征 如输入shape [32,3,32,32] 通过encoder后输出 [32,64,8,8] (其中64位输出维度) 量化码本 先随机构建一个码本&#xff0c;维度…...

OpenAI的ChatGPT:引领人工智能交流的未来

如果您在使用ChatGPT工具的过程中感到迷茫&#xff0c;别担心&#xff0c;我在这里提供帮助。无论您是初次接触ChatGPT plus&#xff0c;还是在注册、操作过程中遇到难题&#xff0c;我都将为您提供一对一的指导和支持。(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.下载好之后把所有的包都传到从节点上&#xff0c;安装 [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 图书借阅系统 窗体项目 期末课程设计 窗体设计

视频教程&#xff1a; 【课程设计】图书借阅系统 功能描述&#xff1a; 图书管理系统有三个角色&#xff0c;系统管理员、图书管理员、借阅者&#xff1b; 系统管理员可以添加借阅用户&#xff1b; ​图书管理员可以添加图书&#xff0c;操作图书借阅和归还&#xff1b; 借…...

2024.01.09.Apple_UI_BUG

我是软件行业的&#xff0c;虽然不是手机设计的&#xff0c;但是这个设计真的导致经常看信息不完整&#xff0c;要下拉的。 特别读取文本或者其他文件的时候&#xff0c;上面有个抬头就是看不到&#xff0c;烦&#xff0c;体验感很差...

K8S Nginx Ingress Controller client_max_body_size 上传文件大小限制

现象 k8s集群中&#xff0c;上传图片时&#xff0c;大于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&#xff09;基础抓取脚本 2&#xff09;抓取物体在手柄上的角度 2.模型放置区域高亮并吸附 1&#xff09;VRTK_SnapDropZone 2&#xff09;VRTK_PolicyList 3&#xff09;VRTK_SnapDropZone_UnityEvents 3.交互滑动条 4.交互旋…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...