POJ3264线段树求最大最小值

2019-11-06 07:39:43

字体：大中小

来源：转载

供稿：网友

#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm>#include<stack>#include<set>#include<map>#include<queue>#include<functional>#include<string>#include<iostream>#include<time.h>/***********************/using namespace std;#define N 300000+3#define NN 40000+10#define INF 0x3f3f3f3f#define mem(arr,num) memset(arr,num,sizeof(arr))#define LL long long int#define PI acos(-1)#define mod 1e9+7int dat[N];int n, num;int MAX, MIN;struct node{ int max, min; int left, right; int mid(){ return (left + right) / 2; }};node tree[N];void init(int n_){ n = 1; while (n < n_)n *= 2;}void build(int root, int left, int right){ int mid = (right + left) / 2; tree[root].left = left; tree[root].right = right; if (left + 1 == right){ tree[root].max = tree[root].min = dat[left]; } else{ build(root * 2 + 1, left, mid); build(root * 2 + 2, mid, right); tree[root].max = max(tree[root * 2 + 1].max, tree[root * 2 + 2].max); tree[root].min = min(tree[root * 2 + 1].min, tree[root * 2 + 2].min); }}void query(int left, int right, int root){ int mid = tree[root].mid(); if (tree[root].left == left&&tree[root].right == right){ MAX = max(tree[root].max, MAX); MIN = min(tree[root].min, MIN); return; } if (left >= mid){ query(left, right, root * 2 + 2); } else if (right <= mid){ query(left, right, root * 2 + 1); } else{ query(left, mid, root * 2 + 1); query(mid, right, root * 2 + 2); }}int main(){ while (~scanf("%d", &n)) { int k; scanf("%d", &k); num = n; init(n); for (int i = 0; i < num; i++)scanf("%d", &dat[i]); build(0, 0, num); while (k--){ int a, b; scanf("%d%d", &a, &b); MAX = -INF; MIN = INF; query(a - 1, b, 0); PRintf("%d/n", MAX - MIN); } }}

上一篇：SSL 1579——泽泽在英国

下一篇：elasticsearch5.2.2 插件开发（一）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注