POJ 2823線分樹の簡単操作


クリックしてリンクを開く
列の配列を与え、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; }