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; } }