http://acm.nyist.net/JudgeOnline/problem.php?pid=119

本文主要是介绍http://acm.nyist.net/JudgeOnline/problem.php?pid=119，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一开始想的是写两个查询一个找最大值，一个找最小值，没想到却tle，，最后写了一个查询，，却莫名其妙的过了，杯具的线段树求法~~~~

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
const int MAX = 0xfffffff;
const int N = 100005;
int maxsum, minsum;
struct segtree
{  int l;int r;int max;int min;
}seg[N << 2];void Build_Tree(int t,int l,int r)
{seg[t].l=l;seg[t].r=r;if(l == r){scanf("%d", &seg[t].max);seg[t].min = seg[t].max;return ;}int m = (l + r) >> 1;Build_Tree(t<<1,l,m);Build_Tree(t<<1|1,m+1,r);seg[t].max = max(seg[t << 1].max, seg[(t << 1) + 1].max);seg[t].min = min(seg[t << 1].min, seg[(t << 1) + 1].min);
}void Query(int t,int l,int r)
{if(l<= seg[t].l && seg[t].r <= r){maxsum = max(maxsum, seg[t].max);minsum = min(minsum, seg[t].min);return ;}if(r<=seg[t<<1].r)  Query(t<<1,l,r);else if(l>seg[t<<1].r)  Query(t<<1|1,l,r);else{Query(t<<1,l,seg[t<<1].r);Query(t<<1|1,seg[t<<1|1].l,r);}}int main()
{int n, q;int a, b;while(scanf("%d%d", &n, &q) != EOF){Build_Tree(1,1,n);while(q--){scanf("%d %d", &a, &b);maxsum = -MAX, minsum = MAX;Query(1,a,b);printf("%d\n", maxsum-minsum);}}return 0;
}

这篇关于http://acm.nyist.net/JudgeOnline/problem.php?pid=119的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---