PKU 2823 - Sliding Window

問題概要

N個の要素をもつ数列が与えられる。
この数列において、K個の要素をもつ区間それぞれについて、最小値・最大値を求めよ。

解法

セグメントツリーを使って、区間の最小値・最大値をO(log n)で求めてしまいましょう。
セグメントツリーは、プログラミングコンテストチャレンジブックを参照してください。

プログラム

セグメントツリーのコードは、アリ本からの転載です。

#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;

typedef pair<int,int> P; //first : min, second : max

const int MAX_N = 1 << 20;

int n;
int datMin[2 * MAX_N - 1];
int datMax[2 * MAX_N - 1];

P ans[MAX_N];

void init(int n_){
  n = 1;
  while(n < n_) n *= 2;
  for(int i = 0; i < 2 * n - 1; i++){
    datMin[i] = INT_MAX;
    datMax[i] = INT_MIN;
  }
}
 
void update(int k, int a){
  k += n - 1;
  datMax[k] = datMin[k] = a;
  while(k > 0){
    k = (k - 1) / 2;
    datMin[k] = min(datMin[k * 2 + 1], datMin[k * 2 + 2]);
    datMax[k] = max(datMax[k * 2 + 1], datMax[k * 2 + 2]);
  }
}

P query(int a, int b, int k, int l, int r){
  if(r <= a || b <= l) return P(INT_MAX, INT_MIN);
  if(a <= l && r <= b) return P(datMin[k], datMax[k]);
  else{
    P vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    P vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return P(min(vl.first, vr.first), max(vl.second, vr.second));
  }
}

int main(){
  int N, K;

  while(cin >> N >> K){
    init(N);

    for(int i = 0; i < N; i++){
      int x;
      scanf("%d", &x);
      update(i, x);
    }

    for(int i = 0; i + K <= N; i++){
      ans[i] = query(i, i + K, 0, 0, n);
    }

    for(int i = 0; i + K <= N; i++){
      if(i != 0) cout << " ";
      cout << ans[i].first;
    }
    cout << endl;

    for(int i = 0; i + K <= N; i++){
      if(i != 0) cout << " ";
      cout << ans[i].second;
    }
    cout << endl;
  }
}