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

第八大奇迹

目录

题目描述

输入描述

输出描述

输入输出样例

示例

输入

输出

运行限制

原题链接

代码思路


题目描述

在一条 R 河流域,繁衍着一个古老的名族 Z。他们世代沿河而居,也在河边发展出了璀璨的文明。

Z 族在 R 河沿岸修建了很多建筑,最近,他们热衷攀比起来。他们总是在比谁的建筑建得最奇特。

幸好 Z 族人对奇特的理解都差不多,他们很快给每栋建筑都打了分,这样评选谁最奇特就轻而易举了。

于是,根据分值,大家很快评出了最奇特的建筑,称为大奇迹。

后来他们又陆续评选了第二奇特、第二奇特、......、第七奇特的建筑,依次称为第二大奇迹、第三大奇迹、......、第七大奇迹。

最近,他们开始评选第八奇特的建筑,准备命名为第八大奇迹。

在评选中,他们遇到了一些问题。

首先,Z 族一直在发展,有的建筑被拆除又建了新的建筑,新建筑的奇特值和原建筑不一样,这使得评选不那么容易了。

其次,Z 族的每个人所生活的范围可能不一样,他们见过的建筑并不是所有的建筑,他们坚持他们自己所看到的第八奇特的建筑就是第八大奇迹。

Z 族首领最近很头疼这个问题,他害怕因为意见不一致导致 Z 族发生分歧。他找到你,他想先了解一下,民众自己认为的奇迹是怎样的。

现在告诉在 R 河周边的建筑的变化情况,以及在变化过程中一些人的生活范围,请编程求出每个人认为的第八大奇迹的奇特值是多少。

输入描述

输入的第一行包含两个整数 𝐿,𝑁L,N,分别表示河流的长度和要你处理的信息的数量。开始时河流沿岸没有建筑,或者说所有的奇特值为 0。

接下来 𝑁N 行,每行一条你要处理的信息。

如果信息为 𝐶 𝑝 𝑥C p x,表示流域中第 𝑝 (1≤𝑝≤𝐿)p (1≤p≤L) 个位置建立了一个建筑,其奇特值为 𝑥x。如果这个位置原来有建筑,原来的建筑会被拆除。

如果信息为 𝑄 𝑎 𝑏Q a b,表示有个人生活的范围是河流的第 𝑎a 到 𝑏b 个位置(包含 𝑎a 和 𝑏b,𝑎≤𝑏a≤b),这时你要算出这个区间的第八大奇迹的奇特值,并输出。如果找不到第八大奇迹,输出 0。

其中,1≤𝐿≤105,1≤𝑁≤1051≤L≤105,1≤N≤105。所有奇特值为 不超过 109109 的非负整数。

输出描述

对于每个为 Q 的信息,你需要输出一个整数,表示区间中第八大奇迹的奇特值。

输入输出样例

示例

输入
10 15
C 1 10
C 2 20
C 3 30
C 4 40
C 5 50
C 6 60
C 7 70
C 8 80
C 9 90
C 10 100
Q 1 2
Q 1 10
Q 1 8
C 10 1
Q 1 10
输出
0
30
10
20

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

原题链接

第八大奇迹icon-default.png?t=N7T8https://www.lanqiao.cn/problems/242/learning/?page=1&first_category_id=1&name=%E7%AC%AC%E5%85%AB%E5%A4%A7%E5%A5%87%E8%BF%B9

代码思路

import java.util.Scanner;public class Main {static Tree[] trees;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int L = scanner.nextInt();int N = scanner.nextInt();// 注意线段树的长度要是存入长度(L)的四倍;trees = new Tree[L << 2];// 构建线段树structure(1, 1, L);while (N-- > 0) {String temp1 = scanner.next();int temp2 = scanner.nextInt();int temp3 = scanner.nextInt();if (temp1.equals("C")) {renew(1, temp2, temp3);} else {System.out.println(query(1, temp2, temp3)[7]);}}}// 构建线段树static void structure(int k, int left, int right) {trees[k] = new Tree(left, right);if (left == right) {return;}int mid = (left + right) >> 1;structure(k << 1, left, mid);structure(k << 1 | 1, mid + 1, right);}// 修改线段树里的数组static int[] modify(int num1[], int num2[]) {int num3[] = new int[8];int a = 0;int b = 0;for (int i = 0; i < num3.length; i++) {// 从两个子节点的数组中赋较大的值给父节点if (num1[a] > num2[b]) {num3[i] = num1[a++];} else {num3[i] = num2[b++];}}return num3;}// 更新线段树static void renew(int k, int i, int value) {if (trees[k].left == trees[k].right) {trees[k].num[0] = value;return;}int mid = (trees[k].left + trees[k].right) >> 1;if (mid >= i) {renew(k << 1, i, value);} else {renew(k << 1 | 1, i, value);}// 更新父亲节点的数组trees[k].num = modify(trees[k << 1].num, trees[k << 1 | 1].num);}// 查询线段树static int[] query(int k, int left, int right) {if (trees[k].left >= left && trees[k].right <= right) {return trees[k].num;}int mid = (trees[k].left + trees[k].right) >> 1;int num[] = new int[8];if (mid >= left) {num = modify(num, query(k << 1, left, right));}if (mid < right) {num = modify(num, query(k << 1 | 1, left, right));}return num;}}class Tree {int left;int right;// 每个节点存一个数组int num[] = new int[8];public Tree(int left, int right) {super();this.left = left;this.right = right;}}

相关文章:

第八大奇迹

目录 题目描述 输入描述 输出描述 输入输出样例 示例 输入 输出 运行限制 原题链接 代码思路 题目描述 在一条 R 河流域&#xff0c;繁衍着一个古老的名族 Z。他们世代沿河而居&#xff0c;也在河边发展出了璀璨的文明。 Z 族在 R 河沿岸修建了很多建筑&#xff0c…...

MySQL:CRUD初阶(有图有实操)

文章目录 &#x1f4d1;1. 数据库的操作&#x1f324;️1.1 显示当前的数据库&#x1f324;️1.2 创建数据库&#x1f324;️1.3 选中数据库&#x1f324;️1.4 删除数据库 &#x1f4d1;2. 表的操作&#x1f324;️2.1 查看表结构&#x1f324;️2.2 创建表&#x1f324;️2.3…...

『大模型笔记』使用 vLLM 和 PagedAttention 快速提供 LLM 服务!

使用 vLLM 和 PagedAttention 快速提供 LLM 服务! 文章目录 一. 使用 vLLM 和 PagedAttention 快速提供 LLM 服务!1.1. PagedAttention二. 参考文献小红书中文字幕视频:https://www.xiaohongshu.com/explore/66502b60000000000500433e官网文档(推荐,里面有动图解释):vLLM:…...

简述vue-loader是什么?使用它的用途有哪些

vue-loader是一个webpack的加载器(loader)&#xff0c;主要用于将Vue组件的单文件(.vue文件)转换为JavaScript模块。使用vue-loader的主要用途包括&#xff1a; 解析.vue文件&#xff1a;vue-loader能够解析.vue文件中的模板、样式和脚本&#xff0c;并将它们分离出来进行处理…...

如何远程访问Redis?

远程访问Redis是一种常见的需求&#xff0c;特别是在分布式系统或跨地域网络中。通过远程访问&#xff0c;我们可以轻松地对远程的Redis数据库进行操作和管理。 天联保障数据安全 对于远程访问Redis的安全性问题&#xff0c;我们可以借助天联来保障数据的安全。天联是一种基于…...

#12松桑前端后花园周刊-SolidStart、Vercel融资、Angular18、Nextjs15RC、p5.js、ChromeDevTools引入AI

⚡️行业动态 SolidStart 1.0 元框架发布 Solidjs 核心团队发布其元框架 SolidStart 1.0 正式版&#xff0c;其特点如下&#xff1a;基于文件系统的路由&#xff1b;支持SSR、流式SSR、CSR、SSG渲染模式&#xff1b;通过代码分割、树摇和无用代码删除构建优化&#xff1b;基于…...

vue3 vite title 页面标题设置

效果图&#xff1a; 1. 安装 vite-plugin-html 插件 npm install vite-plugin-html -D2. 修改 vite.config.js import {defineConfig, loadEnv} from vite import { createHtmlPlugin } from "vite-plugin-html" import {resolve} from path import vue from vitej…...

spring boot添加License(软件许可)

文章目录 前言1. 生成钥匙库2. 生成证书3. 生成公匙库4.业务代码1. 引入依赖2. 关键代码3. 配置文件 5、改成线上地址&#xff0c;这样不用每次打包&#xff0c;发送license.lic文件给客户&#xff0c;重启项目就行5.1、工具类5.2 修改部分&#xff1a; 总结 前言 工作需要给软…...

LangChain打造一个AI客服

最近在学习LangChain&#xff0c;langchain的第一个入门应用就是和ChatGPT结合形成的一个AI客服&#xff0c;本期文章就带大家一起认识下 LangChain LangChain是现在用得最多的AI框架&#xff0c;langchain在帮助如基于文档数据的回答、聊天机器人和代理这类的应用程序 langch…...

【前端三剑客之JS】详解JS

1. JS的引入方式 (1). 内部脚本方式引入 在页面上&#xff0c;通过一对script标签引入js代码.script代码放置位置有一定随意性&#xff0c;一般放在head标签中. (2).外部脚本方式引入. 内部脚本只能在当前页面中使用&#xff0c;代码复用度不高.可以将脚本放在单独的js文件…...

重庆耶非凡科技有限公司有选品师项目培训吗?

在当今科技飞速发展的时代&#xff0c;各种科技公司如雨后春笋般涌现&#xff0c;它们在不同领域发挥着重要作用。其中&#xff0c;重庆耶非凡科技有限公司以其独特的业务模式和专业服务&#xff0c;在业界赢得了良好的口碑。那么&#xff0c;重庆耶非凡科技有限公司究竟是做什…...

格式转化——Labelme标注好的json文件批量转为png(标签)文件(物体为红色,背景为黑色)和jpg原图

作用如题目&#xff0c;批量将标注好的json文件转成png标签&#xff0c;jpg原图&#xff0c;其中标签时红黑图。 代码如下&#xff1a; import argparse import base64 import json import os import os.path as osp import imgviz import PIL.Image import yaml from labelm…...

力扣刷题--2535. 数组元素和与数字和的绝对差【简单】

题目描述 给你一个正整数数组 nums 。 元素和 是 nums 中的所有元素相加求和。 数字和 是 nums 中每一个元素的每一数位&#xff08;重复数位需多次求和&#xff09;相加求和。 返回 元素和 与 数字和 的绝对差。 注意&#xff1a;两个整数 x 和 y 的绝对差定义为 |x - y| 。…...

2024年【危险化学品经营单位安全管理人员】考试报名及危险化学品经营单位安全管理人员找解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 危险化学品经营单位安全管理人员考试报名考前必练&#xff01;安全生产模拟考试一点通每个月更新危险化学品经营单位安全管理人员找解析题目及答案&#xff01;多做几遍&#xff0c;其实通过危险化学品经营单位安全管…...

IntelliJ IDEA集成Baidu Comate,商城系统支付交易功能开发实战

文章目录 Baidu Comate介绍安装配置体验安装插件配置体验注释生成代码技术问答 实战设计表生成代码导入数据 总结 Baidu Comate介绍 在科技互联网飞速发展的今天&#xff0c;百度凭借其深厚的技术积累和创新能力&#xff0c;推出了一款名为Baidu Comate智能代码助手的产品。该…...

20212313 2023-2024-2 《移动平台开发与实践》第5次作业

20212313 2023-2024-2 《移动平台开发与实践》第5次作业 1.实验内容 设计并开发一个地图应用系统。 该实验需提前申请百度API Key&#xff0c;调用接口实现百度地图的定位功能、地图添加覆盖物和显示文本信息。 2.实验过程 2.1 获取SHA1 &#xff08;1&#xff09;打开控制台…...

Python图形界面(GUI)Tkinter笔记(十二):用【Entry()】实现单行文本输入(3)

Tkinter库中的单行文本输入框(Entry)除了与get()方法组合产生多姿多彩的反应,还可以与insert()方法组合而产生新的功能。例如用于用户不作任何输入就用默认值当作用户的输入这种场境,或在输入文本中加入指定的字符等。 其余笔记:【Python图形界面(GUI)Tkinter笔记(总目录…...

前端渲染页面的原理

之前一直不愿意写一篇关于原理的&#xff0c;因为说起来实在是太繁杂&#xff0c;要写得细&#xff0c;码字梳理&#xff0c;计算下来起码都要差不多三周。以前一直躲避这个事情&#xff0c;现在反正有时间&#xff0c;为了不荒废自己&#xff0c;那就从头捋一遍。也方便自己后…...

【一竞技DOTA2】RAMZES666替补参加裂变联赛

1、根据主办方文件,RAMZES666将继续作为Tundra战队替补参加裂变联赛。该比赛为欧洲线上赛,于5月27日-30日举行,总奖金8万美元。 除此之外,Nigma战队在上个月宣布四号位Matthew离队后,也选择启用老队员GH参赛。而在本月初让ah fu转回教练、携替补Thiolicor出战PGL瓦拉几亚的Secr…...

1109 擅长C(测试点0,1,2,3)

当你被面试官要求用 C 写一个“Hello World”时&#xff0c;有本事像下图显示的那样写一个出来吗&#xff1f; ..C.. .C.C. C...C CCCCC C...C C...C C...C CCCC. C...C C...C CCCC. C...C C...C CCCC. .CCC. C...C C.... C.... C.... C...C .CCC. CCCC. C...C C...C C...C C…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...