题目大意：原题链接(定长区间求最值)
给定长为n的数组,求出每k个数之间的最小/大值。
解法一：线段树
segtree节点存储区间的最小/大值
Query_min(int p,int l,int r,int ll,int rr)从编号为p的节点开始在区间[l,r]内查询区间[ll,rr]的最小值
Query_max(int p,int l,int r,int ll,int rr)从编号为p的节点开始在区间[l,r]内查询区间[ll,rr]的最大值
当[l,r]区间完全包含于[ll,rr]区间时,直接return segmin[p]或者return segmax[p].
注意：
1.这两个递归调用时,传入的参数ll和rr始终没有变;
2.这两个函数中的if(rr>mid)不能取"=",比如在区间[1,8]内查询区间[1,4]的最值,因为if(ll<=mid)已经把区间[1,4]的结果给计算出来了,如果加上"=",那么接下来就要在区间[5,8]内查询区间[1,4]的最值了,而区间[1,4]始终<区间[5,8]内的mid,导致程序无法return,崩溃;
3.这两个函数中的int begin=inf;int end=inf;语句和int begin=-inf;int end=-inf语句很关键,比如在区间[1,8]查询内查询区间[1,5]的最值,因为1<=1<=4<=4如上所述区间[1,4]完全包含于区间[1,4];所以区间[1,4]的最值正常返回给begin或者end,但是如果每次递归调用时不重新给begin和end赋值的话,那么叶子节点[5]的值无法正常返回,因为叶子节点[5]返回的值无法和begin或者end比较大小.因为begin和end根本就没有值.
#include<cstdio>
#include<algorithm>
#define maxn 1000005
#define inf 0x3f3f3f3f
using namespace std;
int Segmin[maxn<<],Segmax[maxn<<];
int n,k,value; void Build(int p,int l,int r)
{
if(l==r){
scanf("%d",&value);
Segmax[p]=Segmin[p]=value;
return;
}
int mid=(l+r)/;
Build(*p,l,mid);
Build(*p+,mid+,r);
Segmin[p]=min(Segmin[*p],Segmin[*p+]);
Segmax[p]=max(Segmax[*p],Segmax[*p+]);
}
int Query_min(int p,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr)
return Segmin[p];
int mid=(l+r)/;
int begin=inf,end=inf;
if(ll<=mid)
begin=Query_min(*p,l,mid,ll,rr);
if(rr>mid)
end=Query_min(*p+,mid+,r,ll,rr);
return min(begin,end);
}
int Query_max(int p,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr)
return Segmax[p];
int mid=(l+r)/;
int begin=-inf,end=-inf;
if(ll<=mid)
begin=Query_max(*p,l,mid,ll,rr);
if(rr>mid)
end=Query_max(*p+,mid+,r,ll,rr);
return max(begin,end);
} int main()
{
scanf("%d%d",&n,&k);
Build(,,n);
for(int i=;i<=n-k+;i++)
printf("%d ",Query_min(,,n,i,i+k-));
printf("\n");
for(int i=;i<=n-k+;i++)
printf("%d ",Query_max(,,n,i,i+k-));
printf("\n");
}
#include<cstdio>
#include<algorithm>
#define maxn 1000005
#define inf 0x3f3f3f3f
using namespace std;
int segmin[maxn<<],segmax[maxn<<];
int n,k,value,mi,ma; void Build(int p,int l,int r)
{
if(l==r){
scanf("%d",&value);
segmax[p]=segmin[p]=value;
return;
}
int mid=(l+r)/;
Build(*p,l,mid);
Build(*p+,mid+,r);
segmin[p]=min(segmin[*p],segmin[*p+]);
segmax[p]=max(segmax[*p],segmax[*p+]);
}
void Query_val(int p,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr){
mi=min(mi,segmin[p]);
ma=max(ma,segmax[p]);
return;
}
int mid=(l+r)/;
if(ll<=mid)
Query_val(*p,l,mid,ll,rr);
if(rr>mid)
Query_val(*p+,mid+,r,ll,rr);
} int main()
{
scanf("%d%d",&n,&k);
Build(,,n);
for(int i=;i<=n-k+;i++){
mi=inf,ma=-inf;
Query_val(,,n,i,i+k-);
printf("%d ",mi);
}
printf("\n");
for(int i=;i<=n-k+;i++){
mi=inf,ma=-inf;
Query_val(,,n,i,i+k-);
printf("%d ",ma);
}
printf("\n");
}
解法二：RMQ
因为是定长区间,所以数组d[maxn]被优化,只剩下一维.
#include<cstdio>
#include<algorithm>
#define maxn 1000007
using namespace std;
int c[maxn],d[maxn];
int n,k,t=;
//d[i]表示从i到i+k-1的一段元素中的最小值
void Init1()
{
for(int i=;i<=n;i++)
d[i]=c[i];
for(int j=;j<=t;j++){//j<=t或者(1<<j)<=k
for(int i=;i+(<<j)-<=n;i++)
d[i]=min(d[i],d[i+(<<(j-))]);
}
}
void Init2()
{
for(int i=;i<=n;i++)
d[i]=c[i];
for(int j=;j<=t;j++)
for(int i=;i+(<<j)-<=n;i++)
d[i]=max(d[i],d[i+(<<(j-))]);
} int Query1(int l,int r){
return min(d[l],d[r-(<<t)+]);
}
int Query2(int l,int r){
return max(d[l],d[r-(<<t)+]);
} int main()
{//定长区间(长度为k)查找
scanf("%d%d",&n,&k);
while(<<(t+)<=k) t++;
for(int i=;i<=n;i++)
scanf("%d",&c[i]);
Init1();
for(int i=;i<=n-k+;i++){
if(i!=n-k+)
printf("%d ",Query1(i,i+k-));
else
printf("%d\n",Query1(i,i+k-));
}
Init2();
for(int i=;i<=n-k+;i++){
if(i!=n-k+)
printf("%d ",Query2(i,i+k-));
else
printf("%d\n",Query2(i,i+k-));
}
}
解法三：单调队列
#include<cstdio>
#define maxn 1000005
using namespace std;
struct Que
{
int value;
int index;
}min_que[maxn],max_que[maxn]; int n,k,front,rear,num[maxn];
int max_rear_inc(int f,int r,int d)
{//递增队列,队尾插队
int mid;
while(f<=r){
mid=(f+r)/;
if(min_que[mid].value==d)
return mid;
else if(min_que[mid].value>d)
r=mid-;
else
f=mid+;
}
return f;
}
int min_rear_inc(int f,int r,int d)
{//递减队列,队尾插队
int mid;
while(f<=r){
mid=(f+r)/;
if(max_que[mid].value==d)
return mid;
else if(max_que[mid].value>d)
f=mid+;
else
r=mid-;
}
return f;
}
int main()
{
//while(scanf("%d%d",&n,&k)!=EOF){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d",&num[i]); min_que[].value=num[];
min_que[].index=;
front=,rear=;
for(int i=;i<=k;i++){
rear=max_rear_inc(front,rear,num[i]);
min_que[rear].value=num[i];
min_que[rear].index=i;
}
printf("%d ",min_que[].value);
for(int i=k+;i<=n;i++){
rear=max_rear_inc(front,rear,num[i]);
min_que[rear].value=num[i];
min_que[rear].index=i;
if(min_que[front].index<=i-k)
front++;
printf("%d ",min_que[front].value);
}
printf("\n"); max_que[].value=num[];
max_que[].index=;
front=,rear=;
for(int i=;i<=k;i++){
rear=min_rear_inc(front,rear,num[i]);
max_que[rear].value=num[i];
max_que[rear].index=i;
}
printf("%d ",max_que[].value);
for(int i=k+;i<=n;i++){
rear=min_rear_inc(front,rear,num[i]);
max_que[rear].value=num[i];
max_que[rear].index=i;
if(max_que[front].index<=i-k)
front++;
printf("%d ",max_que[front].value);
}
printf("\n");
//}
return ;
}
#include<cstdio>
using namespace std;
#define maxn 2000005
int n,k;
int mq_min[maxn],mq_max[maxn],pos[maxn],c[maxn];
void get_Min()
{//递增队列
int front=,rear=;
for(int i=;i<k;i++){
while(front<=rear&&mq_max[rear]>=c[i])
rear--;
rear++;
mq_max[rear]=c[i];//新添加的为较大值
pos[rear]=i;
}
for(int i=k;i<=n;i++){
while(front<=rear&&mq_max[rear]>=c[i])
rear--;
rear++;
mq_max[rear]=c[i];
pos[rear]=i;
while(pos[front]<=i-k)
front++;
printf("%d ",mq_max[front]);
}
}
void get_Max()
{//递减队列
int front=,rear=;
for(int i=;i<k;i++){
while(front<=rear&&mq_min[rear]<=c[i])
rear--;
rear++;
mq_min[rear]=c[i];//新添加的为较小值
pos[rear]=i;
}
for(int i=k;i<=n;i++){
while(front<=rear&&mq_min[rear]<=c[i])
rear--;
rear++;
mq_min[rear]=c[i];
pos[rear]=i;
while(pos[front]<=i-k)
front++;
printf("%d ",mq_min[front]);
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d",&c[i]);
get_Min();
printf("\n");
get_Max();
}