POJ 2823線分樹の簡単操作
クリックしてリンクを開く
列の配列を与え、k個当たりの最小値と最大値を求めて出力します.
考え方:一番のモデルの検索は最小値と最大値で、モデルは全部変えなくていいです.
列の配列を与え、k個当たりの最小値と最大値を求めて出力します.
考え方:一番のモデルの検索は最小値と最大値で、モデルは全部変えなくていいです.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1000010;
const int inf=0x3f3f3f3f;
int num[maxn*4],max_num[maxn*4],min_num[maxn*4],L[maxn],R[maxn],max_1,min_1;
void pushup(int node){
max_num[node]=max(max_num[node<<1],max_num[node<<1|1]);
min_num[node]=min(min_num[node<<1],min_num[node<<1|1]);
}
void buildtree(int le,int ri,int node){
if(le==ri){
scanf("%d",&num[node]);
max_num[node]=min_num[node]=num[node];
return ;
}
int t=(le+ri)>>1;
buildtree(le,t,node<<1);
buildtree(t+1,ri,node<<1|1);
pushup(node);
}
void query(int l,int r,int le,int ri,int node){
if(l<=le&&ri<=r){
max_1=max(max_1,max_num[node]);
min_1=min(min_1,min_num[node]);
return ;
}
int t=(le+ri)>>1;
if(l<=t) query(l,r,le,t,node<<1);
if(r>t) query(l,r,t+1,ri,node<<1|1);
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=-1){
buildtree(1,n,1);
for(int i=1;i+m<=n+1;i++){
max_1=-inf,min_1=inf;
query(i,i+m-1,1,n,1);
L[i]=min_1;R[i]=max_1;
}
for(int i=1;i+m<=n+1;i++){
if(i+m==n+1) printf("%d
",L[i]);
else printf("%d ",L[i]);
}
for(int i=1;i+m<=n+1;i++){
if(i+m==n+1) printf("%d
",R[i]);
else printf("%d ",R[i]);
}
}
return 0;
}