首页 > 代码库 > TreeSegment2823_RMQ
TreeSegment2823_RMQ
题目描述：
有N个数，每次从左到右选取M个数，第一行选取每个区间中的最小值输出，第二行选取最大值并输出。
线段树：
#include <iostream>
#include <stdio.h>
using namespace std;
int a[1000005];
int n,k;
struct node
{
int left ;
int right;
int max;
int min;
};
node tree[1000005*4];
int MIN[1000005],MAX[1000005];
int Max(int a,int b)
{
return a>b?a:b;
}
int Min(int a,int b)
{
return a>b?b:a;
}
void build(int left,int right,int root)// build(1,n,1);
{
tree[root].left=left;//这个要首先写
tree[root].right=right;
if(left==right)
{
tree[root].max=tree[root].min=a[left];
return ;
}
int mid=(left+right)/2;
build(left,mid,root*2);
build(mid+1,right,root*2+1);
tree[root].max=Max(tree[root*2].max,tree[root*2+1].max);
tree[root].min=Min(tree[root*2].min,tree[root*2+1].min);
}
void query(int left,int right, int root, int &min,int &max)// query(i,i+k-1,1,MIN[i],MAX[i]);
{
if(tree[root].left==left && tree[root].right==right)
{
max=tree[root].max;
min=tree[root].min;
return ;
}
int mid=(tree[root].left+tree[root].right)/2;//注意这里的mid使用root的left和right来求的
if(right<=mid)
{
query(left,right,root*2,min,max);
}
else if(left>mid)
{
query(left,right,root*2+1,min,max);
}
else
{
int min1,max1;
query(left,mid,root*2,min1,max1);//从左右两边取更小的那个
query(mid+1,right,root*2+1,min,max);
min=Min(min,min1);
max=Max(max,max1);
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,n,1);
for(int i=1;i<=n-k+1;i++)
{
query(i,i+k-1,1,MIN[i],MAX[i]);//对区间[i,i+k-1]求两个极值，存在MIN[I],MAX[I]
}
for(int i=1;i<=n-k+1;i++)//输出
{
printf("%d ",MIN[i]);
}
printf("\n");
for(int i=1;i<=n-k+1;i++)
{
printf("%d ",MAX[i] );
}
printf("\n");
return 0;
}
TreeSegment2823_RMQ