[hihocoder 1070]RMQ问题再临

2023-12-15 23:38
文章标签 问题 rmq hihocoder 1070 再临

本文主要是介绍[hihocoder 1070]RMQ问题再临,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述

终于,小Hi和小Ho踏上了回国的旅程。在飞机上,望着采购来的特产——小Hi陷入了沉思:还记得在上上周他们去超市的时候,前前后后挑了那么多的东西,都幸运的没有任何其他人(售货员/其他顾客)来打搅他们的采购过程。但是如果发生了这样的事情,他们的采购又会变得如何呢?

于是小Hi便向小Ho提出了这个问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品),面对这样一个问题,小Ho又该如何解决呢?

提示:平衡乃和谐之理

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第1行为一个整数N,意义如前文所述。

每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。

每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。

每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi

对于100%的数据,满足N<=10^4,Q<=10^4, 1<=Li<=Ri<=N,1<=Pi<=N, 0

算法详解

穷搜即可,但是作者想要练习一下线段树,下面就是利用线段树解题(或者说作者自己理解的,作者在码代码之前只简略的看了一下相关博客,然后自己实现了一下)。作者对于线段树的理解是主要在于可以对二分搜索的剪枝,所以事先构造一个二分搜索树,存储中间变量,对于新的搜索则尽可能利用中间变量剪枝。

全部代码

#include <iostream>
#include <queue>
#include <stack>
#include <cstdlib>
#include <time.h>using namespace std;int arr[10002],N;struct Node {int mmin;int l,r;Node *left, *right;Node():mmin(-1),l(-1),r(-1),left(NULL),right(NULL) {}Node(int ll,int rr):mmin(-1),l(ll),r(rr),left(NULL),right(NULL) {}~Node() {}Node(const Node &n):mmin(n.mmin),l(n.l),r(n.r),left(n.left),right(n.right) {}void print() {cout << l << '\t' << r << '\t' << mmin << endl;}
};struct Tree {Node *root;Tree():root(NULL) {}Tree(const Tree &t):root(t.root) {}~Tree() {clean(root);}void clean(Node*r) {if (!r)return;clean(r->left);clean(r->right);delete r;}void build_tree(Node* n) {if (n->l == n->r) {n->mmin = arr[n->l];return;}if (n->l == n->r-1){n->left = new Node(n->l,n->l);n->right = new Node(n->r,n->r);n->left->mmin = arr[n->l];n->right->mmin = arr[n->r];n->mmin = min(arr[n->l],arr[n->r]);}int mid = (n->l+n->r)/2;n->left = new Node(n->l,mid);build_tree(n->left);n->right = new Node(mid+1,n->r);build_tree(n->right);n->mmin = min(n->left->mmin,n->right->mmin);}void build_tree() {clean(root);root = new Node(0,N-1);build_tree(root);}int get_min(int l,int r) {return get_min(root,l,r);}int get_min(Node*n,int l,int r) {if (l == r) {return arr[l];}if (l == r-1) {return min(arr[l],arr[r]);}if (r < n->right->l)return get_min(n->left,l,r);if (l > n->left->r)return get_min(n->right,l,r);if (l == n->l && r == n->r)return n->mmin;return min(get_min(n->left,l,n->left->r),get_min(n->right,n->right->l,r));}void update_node(int index,int value) {Node *n = root;stack<Node*> s;while (n->l != n->r) {s.push(n);if (index < n->right->l)n = n->left;elsen = n->right;}n->mmin = value;arr[index] = value;while (!s.empty()) {n = s.top();s.pop();n->mmin = min(n->left->mmin,n->right->mmin);
//            cout << n->l << ' ' << n->r << ' ' << n->mmin << endl;}}void print_tree() {cout << "Tree: " << endl;queue<Node*> q;q.push(root);Node* tmp;while (!q.empty()) {tmp = q.front();q.pop();tmp->print();if (tmp->left)q.push(tmp->left);if (tmp->right)q.push(tmp->right);}}
};/***search***/
int get_min(int l,int r){int result = arr[l];for (int i = l;i <= r;++i)if (result > arr[i])result = arr[i];return result;
}void print_arr() {cout <<  "N: " << N << endl;for (int i = 0;i < N;++i)cout << arr[i] << ' ';cout << endl;}/***test***/
void test() {int seed = (int)time(0);
//    seed = 1483006823;cout << "seed: " << seed << endl;srand(seed);N = rand() % 20;for (int i = 0;i < N;++i)arr[i] = rand()%100;print_arr();Tree tree;tree.build_tree();int Q=rand()%20;int n1,n2,n3;for (int i = 0;i < Q;++i){n1 = rand()%2;if (n1 == 0) {n2 = rand()%N+1;n3 = rand()%N+1;if (n2 > n3) swap(n2,n3);if (tree.get_min(n2-1,n3-1) != get_min(n2-1,n3-1)) {print_arr();cout << n1 << ' ' << n2 << ' ' << n3 << ' ' << tree.get_min(n2-1,n3-1) << ' ' << get_min(n2-1,n3-1) << endl;}}else {n2 = rand()%N+1;n3 = rand()%100;tree.update_node(n2-1,n3);if (arr[n2-1] != n3)cout << n1 << ' ' << n2 << ' ' << n3 << ' ' << arr[n2-1] << endl;}}
}int main()
{Tree tree;cin >> N;for (int i = 0;i < N;++i)cin >> arr[i];tree.build_tree();
//    tree.print_tree();int Q;cin >> Q;int n1,n2,n3;for (int i = 0;i < Q;++i) {cin >> n1 >> n2 >> n3;if (n1 == 0) {cout << tree.get_min(n2-1,n3-1) << endl;}else {tree.update_node(n2-1,n3);}}/***test***/
//    test();return 0;
}

这篇关于[hihocoder 1070]RMQ问题再临的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符