• POJ 3264：Balanced Lineup（线段树应用：区间最大值与最小值之差） 题目链接：POJ 3264 Description For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One ...
POJ 3264：Balanced Lineup（线段树应用：区间最大值与最小值之差）
题目链接：POJ 3264

Description

For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2…N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2…N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1…Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0
题目大意：给定n，q分别表示区间的大小为：n，后跟着q次查询；求得给定区间最大值与最小值之差，暴力绝对不行，线段树简单应用
ps：感觉第二个代码容易懂
代码一如下：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0xffffff0;
const int maxN=200010;
int minV=INF;
int maxV=-INF;     //表示某一区间内最大值、最小值

/**结点结构*/
struct Node
{
int L,R;
int minV,maxV;
int Mid;
/**如果防止内存超限的话可以
int Mid()
{
return (L+R)/2;
}*/
};
/**用数组代替指针存放树结构（只需保证数组大小为结点数4倍即可）*/
Node tree[4*maxN];

/**建立线段树*/
void build_Tree(int root,int L,int R)
{
tree[root].L=L;
tree[root].R=R;

/*如果用第二种方法的话，这条语句就该去掉*/
tree[root].Mid=(tree[root].L+tree[root].R)/2;

tree[root].minV=INF;
tree[root].maxV=-INF;
if(L!=R)
{
build_Tree(2*root,L,(L+R)/2);
build_Tree(2*root+1,(L+R)/2+1,R);
}
}

/**插入数据（将第i个数，其值为v，插入线段树）*/
void Insert(int root,int i,int v)
{
if(tree[root].L==tree[root].R)
{
tree[root].minV=tree[root].maxV=v;
return;
}
tree[root].minV=min(tree[root].minV,v);
tree[root].maxV=max(tree[root].maxV,v);
if(i<=tree[root].Mid)
Insert(2*root,i,v);
else
Insert(2*root+1,i,v);
}

/**查询（查询区间[s,e]中的最小值和最大值，如果更优就记在全局变量minV，maxV里*/
void Query(int root,int s,int e)
{
if(tree[root].minV>=minV&&tree[root].maxV<=maxV)
return ;
if(tree[root].L==s&&tree[root].R==e)
{
minV=min(minV,tree[root].minV);
maxV=max(maxV,tree[root].maxV);
return;
}
/**区间过大*/
if(e<=tree[root].Mid)
Query(2*root,s,e);
else if(s>tree[root].Mid)
Query(2*root+1,s,e);
/**左右子树*/
else
{
Query(2*root,s,tree[root].Mid);
Query(2*root+1,tree[root].Mid+1,e);
}
}
int main()
{
int n,q;
int num;
scanf("%d%d",&n,&q);
build_Tree(1,1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&num);
Insert(1,i,num);
}
for(int i=1;i<=q;i++)
{
int s,e;         //待查询区间起终点
scanf("%d%d",&s,&e);
minV=INF;
maxV=-INF;
Query(1,s,e);
printf("%d\n",maxV-minV);
}
return 0;
}


另附第二种代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF=0xffffff0;     //确定一个最大值
const int maxn=50010;      //n的最大值
/**结点结构*/
struct Node
{
int L,R;
int minV,maxV;
};

Node tree[4*maxn];        //用数组表示线段树
int a[maxn];             //存放结点数值

int maxV=-INF;
int minV=INF;      //存放最大值与最小值

/**建立线段树，并赋初值*/
void build_Tree(int root,int L,int R)
{
tree[root].L=L;
tree[root].R=R;
/**到叶子结点时附值*/
if(L==R)
{
tree[root].maxV=tree[root].minV=a[L];
return ;
}

int mid=(tree[root].L+tree[root].R)/2;
build_Tree(2*root,L,mid);
build_Tree(2*root+1,mid+1,R);

tree[root].minV=min(tree[2*root].minV,tree[2*root+1].minV);
tree[root].maxV=max(tree[2*root].maxV,tree[2*root+1].maxV);          //当不是叶子结点时，存放左右孩子的最大值与最小值
}
/**查询区间[s,e]中的最大值与最小值*/
void  Query(int root,int s,int e)
{
if(minV<=tree[root].minV&&maxV>=tree[root].maxV)
return;

/**当刚好区间相等时*/
if(tree[root].L==s&&tree[root].R==e)
{
minV=min(minV,tree[root].minV);
maxV=max(maxV,tree[root].maxV);
return ;
}

int mid=(tree[root].L+tree[root].R)/2;
/**区间过大时*/
if(e<=mid)
Query(2*root,s,e);
else if(s>mid)
Query(2*root+1,s,e);
/**左右孩子*/
else
{
Query(2*root,s,mid);
Query(2*root+1,mid+1,e);
}
}
int main()
{
int n,q;
int num;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}

build_Tree(1,1,n);

int s,e;
for(int i=1;i<=q;i++)
{
minV=INF;
maxV=-INF;
scanf("%d%d",&s,&e);
Query(1,s,e);
printf("%d\n",maxV-minV);
}
return 0;
}




展开全文
• http://poj.org/problem?id=3264 #include #include #include #include using namespace std; #define L(x) (x ) #define R(x) (x | 1) #define INT_MAX 0x7fffffff const int MAX = 50010;...struct Tnode
http://poj.org/problem?id=3264
#include <cmath>
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define L(x) (x << 1)
#define R(x) (x << 1 | 1)
#define INT_MAX 0x7fffffff
const int MAX = 50010;
struct Tnode
{
int mmax,mmin,val;
int l,r;
};
Tnode node[MAX*3];
int v[MAX],big,small;
void init()
{
memset(node,0,sizeof(node));
}
void build(int t,int l,int r)
{
node[t].l=l;
node[t].r=r;
if(l==r-1)
{
node[t].mmin=v[l];
node[t].mmax=v[l];
return ;
}
int mid =(l+r)>>1;
build(L(t),l,mid);
build(R(t),mid,r);
node[t].mmax=max(node[L(t)].mmax,node[R(t)].mmax);
node[t].mmin=min(node[L(t)].mmin,node[R(t)].mmin);
}
void get(int t,int l,int r)
{
if(node[t].l==l&&node[t].r==r)
{
big=max(node[t].mmax,big);
small=min(node[t].mmin,small);
return ;
}
int mid=(node[t].l+node[t].r)>>1;
if(l>=mid)
get(R(t),l,r);
else if(r<=mid)
get(L(t),l,r);
else
{
get(R(t),mid,r);
get(L(t),l,mid);
}
}
int main()
{
int n,m,x,y;
while( ~scanf("%d%d",&n,&m))
{
init();
for(int i=1; i<=n; i++)
scanf("%d",&v[i]);
build(1,1,n+1);
while(m--)
{
scanf("%d%d",&x,&y);
small=INT_MAX; big=0;
get(1,x,y+1);
printf("%d\n",big-small);
}
}
return 0;
}

展开全文
• 就是一个把求区间最大值与最小值结合起来，我用了两次查询就过了。。。。 #include #include #include #include #include #include #include #include #include #define INF 0x3f3...
Description

For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output

6
3
0

就是一个把求区间最大值与求最小值结合起来，我用了两次查询就过了。。。。

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <cmath>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 200005
#define Mod 10001
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn=222222;
int MAX[maxn<<2],MIN[maxn<<2];
void PushUp(int rt)
{
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(r==l)
{
scanf("%d",&MAX[rt]);
MIN[rt]=MAX[rt];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
PushUp(rt);
}
int queryma(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return MAX[rt];
}
int m=(l+r)>>1;
int ret=0;
if(L<=m)
ret=max(ret,queryma(L,R,lson));
if(R>m)
ret=max(ret,queryma(L,R,rson));
return ret;
}
int querymi(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return MIN[rt];
}
int m=(l+r)>>1;
int ret=INF;
if(L<=m)
ret=min(ret,querymi(L,R,lson));
if(R>m)
ret=min(ret,querymi(L,R,rson));
return ret;
}
int main()
{
int n,q;
while(~scanf("%d%d",&n,&q))
{
build(1,n,1);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",queryma(l,r,1,n,1)-querymi(l,r,1,n,1));
}
}
return 0;
}

展开全文
• ：查询区间最大值或者最小值 这里用ST表处理 ST表(动态规划的思想） 设f [i][st],i为元素起始下标，st为从i开始，长度为2^st的最大值 1.预处理 f[i][0]为从i开始，长度为2^0范围的最大值 for(int i=1;i<=...
RMQ问题

：查询区间最大值或者最小值

这里用ST表处理

ST表(动态规划的思想）

设f [i][st], i为元素起始下标，st为从i开始，长度为2^st 的最大值

1.预处理

f[i][0] 为从i 开始，长度为2^0 范围的最大值

for(int i=1;i<=n;i++){
f[i][0]=a[i];
}

2.  f[i][0]    [i,i]

f[i][1]    [i,i+1]  = max( f[i][0], f[i+2^0][0] )

f[i][2]    [i,i+3]  = max( f[i][1],f[i+2^1][1] )

f[i][3]    [i,i+7]   = max( [i,i+3], [i+4,i+7] ) = max( f[i][2],f[i+2^2][2] )

可以看出，对于区间为[i,st] 的区间，可以拆为 f[i][st-1]  和 f[i+2^(st-1)][st-1])

其实就是将区间对半，然后将两个半区间再比较最大值

循环下界问题

1.  这里的 j 的上限为 2^j<=n,  (1<<j 表示2^j)

关于1<<j 的解释

1 左移 j 位
这是移位运算，左移
1<<1 表示把 二进制 数 0001 左移 1 位，变成 0010， 等于 2
1<<4 表示把 二进制 数 0001 左移 4 位，变成 0001 0000， 等于 16

2.  i 的坐标也不能越界，i+2^j <= n+1具体解释看大佬博客

for(j=1;(1<<j)<=n;++j)
for(i=1;i+(1<<(j-1))<=n;++i)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);


至于查询，设k=log(r- l +1),则 因为k为下取整结果，最后可能长度不能覆盖（r-l+1），例如区间为[1,12]

而k最大=3 ，长度为8，到不了12，

所以用max( f[l][k] ,f[r-(1<<k)+1][k] ) ，即max( [1,8] , [5,12] )

以m为底的log函数表达式为 log(n)/log(2)或者直接写成 log2(n)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int f[maxn][25];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][0]=a[i];
}
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i<=(n-(1<<j)+1);i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
int l,r,k;
for(int i=1;i<=m;i++){
scanf("%d %d",&l,&r);
k=log(r-l+1)/log(2);
int b=max(f[l][k],f[r-(1<<k)+1][k]);
printf("%d\n",b);
}
return 0;
}


展开全文
• matlab求函数在区间最大值与最小值 我用了fminbnd这个函数使用方法如下 详细信息[官方文档] 方法一 fun = @sin; x1 = 0; x2 = 2*pi; x = fminbnd(fun,x1,x2) 结果 x = 4.7124 %返回的是当极小值点 方法二 求 ...
• 这个题意翻译一下就是：区间最大值-区间最小值+1=区间不同值的个数 那么我们用线段树维护最大值-最小值-不同值的个数。那么答案就是这个区间有多少值是-1即可，然而由于最大值-最小值+1是一定大约等于区间不同值的...
• 求数组所有区间最大值减去最小值之差的和(贝壳笔试题) 思路1： 暴力O(N^3)， def jicha(list1,n): sum1=0 temp_dic={} for i in range(n): for j in range(n): if(i&amp;lt;j): sij = str(i) + str...
• 这个题直接暴力求解的话时间复杂度肯定是不行的，所以，我们要计算每个数值的贡献，对每一个数求他当最小值当了多少次，当最大值当了多少次，最后当最大值的次数乘以这个数值减去当最小值的次数乘以数值就得到这个数...
• 动态区间最大值最小值区间和查询，支持区间设置，线段树 对区间 [0,N-1] 支持两种操作： 1. update(L, R, v) 将区间[L,R] 的所有值设置为 v； 2. query(L, R) 查询区间 [L, R] 的最大值、最小值、区间和...
• 最大值最小值 获取作者年龄的最大值最小值 分组查询 每个个图书销量的最高价最低价
• /*RMQ 更新最小值操作 By:draymonder*/ #include #include using namespace std; const int mod = 1e9 + 7; const int maxn = 1 17; const int INF = 0x3f3f3f3f; typedef long long LL; int n,s[2*...
• 虽然线段树和树状数组也可以求解区间最大值最小值，但是他们确没有st表的速度快，st表预处理之后查询区间最大最小值只要O（1）的时间，st表的精要就是dp数组的特点，dp[i][j]表示的是从i开始，长度为2^j长度的区间...
• } // 求区间内的最大值 int Q_min(int l, int r) { int k = (int)(log(double(r - l + 1)) / log((double)2)); return min(a_min[l][k], a_min[r - (1 ) + 1][k]); } // 求区间内的最小值 int main() { ios::sync...
• 题意：求解区间【a,b】内最大值最小值的差值 解题思路：建立线段树，每个节点包含max和min，再按照一般线段树的方法即可 #include "stdio.h" #include "stdlib.h" #define N 50005 int man,mnn; int maxn(int...
• 现在 ZJM 想知道在窗口从左往右滑的时候，每次窗口内数的最大值最小值分别是多少. 例如： 数列是 [1 3 -1 -3 5 3 6 7], 其中 k 等于 3. Input 输入有两行。第一行两个整数n和k分别表示数列的长度和滑动窗口的...
• layui两个时间选择框如何设置最大值与最小值 问题描述： layui设置两个时间选择框如何设置它们的选择范围 解决方案： var start = laydate.render({ elem: id , done: function (value, date, endDate) { ...
• 2. query(L, R) 查询区间 [L, R] 的最大值最小值区间和； 利用线段树解决该问题，更新时，对某区间的设置操作不需要分解到其每一个子区间（否则可能要更新每一个叶子节点），只需在该区间上做设置标记；在查询...
• 函数的最大值最小值说课稿...　【教材分析】　1、本节教材的地位作用　本节主要研究闭区间上的连续函数最大值最小值的求法和实际应用，分两课时，这里是第一课时，它是在学生已经会求某些函数的最值，并且已...
• 题意：给定长度为n的序列a和一个整数K,找出最大值最小值的差值小于K的区间。输出满足条件的区间的个数。 分析：枚举a[i],以a[i]为起点,然后二分找终点(大区间满足条件的话小区间肯定也满足),根据起点和终点的位置...
• 题意： 给你n个数，和k，让你把这n个数（连续）划分成k个区间，每个区间都选择一个最小值，让后让你从最小值中的最大值最大。 思路：当k等于1的时候，我们直接输出最小值就好，当k大于3的时候，我们直接输出一个...
• //区间最大值 int mn; //区间最小值 }tree[MAXN];//一定要开到4倍多的空间 void pushup(int index){ tree[index].sum = tree[index].sum+tree[index|1].sum; tree[index].mx = max(tree[index].mx,tree...
• 整体思路： 将数组划分成两半，分别找出两边的最小值与最大值，两边局部最小值中较小的那个为整体最小值，两边局部最大值中较大的为...由于是递归实现需要考虑终止条件：当区间容量为2或1时，获取局部最小值与最大值
• 绝对值函数与最大值/最小值函数之间的关系
• EXCEL根据条件取最大值最小值
• 用粒子群优化算法求解函数最大值最小值问题，稍微更改一下即可求任意函数最值 用粒子群优化算法求解函数最大值最小值问题，稍微更改一下即可求任意函数最值
• 微信小程序用canvas实现区间滑动选取，最小值最大值wx-canvas--master.zip
• 在一个线性序列中同时求出最大值最小值 题目描述:在一个线性序列中同时求出最大值最小值；  方法一:初时看到这个题目，第一想法就是设定一个初始的最大值最小值,然后循环遍历数组,进行比较，如下所示:  #...

...