[hihocoder 1070]RMQ问题再临

本文主要是介绍[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;
}