第八大奇迹

2024-05-28 07:20
文章标签 奇迹 第八

本文主要是介绍第八大奇迹,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

题目描述

输入描述

输出描述

输入输出样例

示例

输入

输出

运行限制

原题链接

代码思路


题目描述

在一条 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;}}

这篇关于第八大奇迹的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1009904

相关文章

重生奇迹MU老大哥剑士职业宝刀未老

重生奇迹MU中,老大哥剑士职业一直以来备受玩家们的喜爱。这个职业不仅拥有强大的攻击力、防御力和战斗技巧,而且还能够通过使用各种宝刀来增强自身的战斗能力。即便经过了多年的沉淀,老大哥剑士依然是一名宝刀未老的男人,仍然能够在战场上力挽狂澜。如果你是一名重生奇迹MU玩家,不妨选择老大哥剑士职业,体验一下宝刀未老的快感! 人们常常怀念过去,那是因为过去有深刻的记忆。在重生奇迹MU里,最令人难忘的职业便是

第八题:字符串转换整数 (atoi)

题目描述 实现 myAtoi(string s) 函数,将字符串转换成 32 位有符号整数。函数首先丢弃字符串前面的空格字符,直到找到第一个非空格字符为止。然后,选择该非空格字符和之后的连续字符组成一个存储整数的字符串。字符串可以包含额外字符,这些字符在形成整数的字符串后面,并被忽略。如果第一个非空格字符不是数字且不是符号+ 或者-,则不进行转换并返回 0。如果转换过程中存在任何无法识别的字符,

C++奇迹 2024年6月c++一级 电子学会中小学生软件编程C++等级考试一级真题答案解析

目录 C++奇迹 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C++奇迹 2024年6月 C++编程等级考试一级编程题 一、题目要求 1、编程实现 经典电影《阿甘正传》有句台词,说:"Miracles happen every day.”(奇迹每天都发生)。本题就请你直接在屏幕上输出这句话。

暴力出奇迹

LA4253 Archery 二分,给出n条水平线段,问能否在[0,w]区间选一个点当发出一条射线穿过所有的线段,先把线段按高度排序,然后二分射线起点的位置。 http://acm.bnu.edu.cn/v3/problem_show.php?pid=11135 #include <bits/stdc++.h>using namespace std;const int maxn =

Java进阶13讲__第八讲

集合:Collection,List,Set,Map 集合体系 集合结构 单列集合 1.Collection 1.初识Collection package cn.hdc.oop8.Collection;import java.util.ArrayList;import java.util.HashSet;import java.util.List;/*** 目

再次进阶 舞台王者 第八季完美童模全球赛首席星推官【张誉馨】赛场秀场超燃合集

7月20-23日,2024第八季完美童模全球总决赛在青岛圆满落幕。在盛大的颁奖典礼上,一位才能出众的少女——张誉馨迎来了她舞台生涯的璀璨时刻。 开场秀初登场,风采惊艳四座!首席星推官——张誉馨,以璀璨童星之姿,优雅地踏上完美童模盛宴的绚丽舞台,作为开场小嘉宾,她瞬间成为了全场瞩目的焦点。她以一种超越年龄的自信与风度,展现了非凡的T台魅力,每一步都踏着星光,精准而富有感染力,仿佛天

第八十四题 (百度面试题)

2010 年3 道百度面试题[相信,你懂其中的含金量] 1 a~z 包括大小写与0~9 组成的N 个数, 用最快的方式把其中重复的元素挑出来。 2.已知一随机发生器,产生0 的概率是p,产生1 的概率是1-p,现在要你构造一个发生器,使得它构造0 和1 的概率均为1/2;构造一个发生器,使得它构造1、2、3 的概率均为1/3;...,构造一个发生器,使得它构造1、2、3、...n 的概率均为1

羊皮卷之四:我是自然界最伟大的奇迹

本文固定连接:http://blog.csdn.net/u013108312/article/details/53579226 我是自然界最伟大的奇迹。   自从上帝创造了天地万物以来,没有一个人和我一样,我的头脑、心灵、眼睛、耳朵、双手、头发、嘴唇都是与众不同的。言谈举止和我完全一样的人以前没有,现在没有,以后也不会有。虽然四海之内皆兄弟,然而人人各异。我是独一无二的造化。   我是自然界

重生奇迹MU敏捷流梦幻骑士

“梦幻骑士”这个职业已经存在于重生奇迹MU中很长时间了,虽然现在已经不算是新职业了,但玩家们对于梦幻骑士的研究和开发一直没有停止过。它作为一个特殊的职业,与传统职业截然不同,拥有着许多独特的玩法。其中,有一种玩法是所有平民玩家的最爱。 敏捷流是目前普遍受欢迎的幻想骑士游戏职业,尤其适合平民玩家选择。它不需要过多的资金投入,只需要将大部分升级点数分配到“敏捷”属性即可。但是,它却能带给玩家出乎意料