本稿では、配列ベースのデータ構造におけるブロック分割（Block Decomposition）の概念と、様々な問題への応用について解説します。ブロック分割は、配列を一定サイズの小ブロックに分割し、各ブロックに対して集約情報や遅延更新メカニズムを導入することで、区間操作や点操作の計算量をバランス良く最適化する手法です。
ブロック分割の基本
配列を長さ約 \\(B\\) のブロックに分割します。これにより、配列全体は約 \\(N/B\\) 個のブロックに分かれます。操作対象の区間が複数のブロックにまたがる場合、「完全に区間内に含まれるブロック」（整塊）と「区間と一部が重なるブロック」（散塊）に分けて処理を行います。
- 完全ブロック（整塊）: ブロック全体に影響する操作は、ブロックごとの集約情報や遅延更新（lazy tag）によって \\(O(1)\\) もしくは \\(O(\\log B)\\) で処理できます。
- 部分ブロック（散塊）: 区間の両端に位置し、一部の要素のみが操作対象となるブロックは、個々の要素に対して直接操作を行う「素朴な（brute-force）処理」を適用します。これにより、各部分ブロックの処理は \\(O(B)\\) となります。
全体の計算量は、通常 \\(O(N/B)\\) と \\(O(B)\\) の項の和として表現され、\\(B = \\sqrt{N}\\) と設定することで \\(O(\\sqrt{N})\\) に最適化されることが多くなります。
問題1: 区間加算と区間合計値クエリ
指定された区間内の全要素に値を加算し、また指定された区間内の全要素の合計値を求める問題です。
データ構造:
- 各ブロックごとに、ブロック内の要素の合計値 (
blockSum) を保持します。 - 各ブロックごとに、そのブロック全体に適用すべき遅延加算値 (
lazyAdd) を保持します。
更新操作 (区間 \\([L, R]\\) に \\(V\\) を加算):
- 区間の両端を含む部分ブロックについて:
- 当該ブロックの
lazyAddを個々の要素に反映（「展開」または「flush」と呼びます）。 - 区間内の該当要素に \\(V\\) を直接加算します。
- ブロックの
blockSumを再計算します。
- 当該ブロックの
- 区間内に完全に含まれる完全ブロックについて:
- 当該ブロックの
lazyAddに \\(V\\) を加算します。 blockSumに \\(V \\times B\\) を加算します（ここで \\(B\\) はブロックサイズ）。
- 当該ブロックの
合計値クエリ (区間 \\([L, R]\\) の合計値を計算):
- 区間の両端を含む部分ブロックについて:
- 当該ブロックの
lazyAddを個々の要素に反映。 - 区間内の該当要素の値を合計します。
- 当該ブロックの
- 区間内に完全に含まれる完全ブロックについて:
blockSum + lazyAdd \\times Bを合計に加算します。
計算量: 各操作において、部分ブロックの処理は \\(O(B)\\) 、完全ブロックの処理は \\(O(N/B)\\) となります。したがって、更新およびクエリの計算量はそれぞれ \\(O(B + N/B)\\) となり、\\(B = \\sqrt{N}\\) とすると \\(O(\\sqrt{N})\\) になります。
注意: 元の問題Aの記述ではクエリが \\(O(1)\\) とされていますが、一般的な区間合計値クエリでは \\(O(\\sqrt{N})\\) が必要です。おそらく、非常に限定的なクエリの場合を指しているか、記述ミスと考えられます。
問題2: 区間加算と区間合計値クエリ（更新 \\(O(1)\\), クエリ \\(O(\\sqrt{N})\\) の場合）
これは、更新とクエリの計算量のバランスを問題1とは逆にしたバリエーションです。更新をほぼ \\(O(1)\\) に近づけ、クエリ時にまとめて処理します。
データ構造:
- 各ブロックに遅延加算値 (
lazyAdd) を保持。 - さらに、各ブロックの開始と終了をまたぐような区間更新のために、ブロック間の差分（例: ブロック境界での累積加算値の変化）を管理する仕組みを導入します。
更新操作 (区間 \\([L, R]\\) に \\(V\\) を加算):
- 区間の両端を含む部分ブロックについて:
- ブロック内の該当要素に差分値を直接適用し、ブロックの合計値を更新します。
- 区間内に完全に含まれる完全ブロックについて:
- 該当ブロックの
lazyAddを更新します。
- 該当ブロックの
- 区間の開始と終了ブロックに対して、そのブロック全体を対象とする差分マーカー（例えば、次のクエリでこのブロック全体に影響を与えるための情報）をセットします。
この更新方法は、各ブロックの内部構造を深く変更しないため、\\(O(1)\\) の計算量で更新できる可能性があります。ただし、詳細な実装には複雑さが伴います。
合計値クエリ (区間 \\([L, R]\\) の合計値を計算):
クエリ時には、影響を受ける全てのブロックを走査し、各ブロックの lazyAdd やその他の差分マーカーの効果を合計に反映させます。必要に応じて、部分ブロックの要素を直接走査して合計を計算します。処理後、差分マーカーをクリアします。
計算量: 更新は \\(O(1)\\) を目指しますが、クエリは \\(O(B + N/B)\\) となり、\\(B = \\sqrt{N}\\) とすると \\(O(\\sqrt{N})\\) になります。
問題3: 値域が線形な場合の単一点挿入とグローバルなk番目要素クエリ
配列に単一の値を挿入し、配列全体の中でk番目に大きい要素を求める問題です。値の範囲 (値域) が比較的狭い線形な場合を想定します。
データ構造:
- 値域自体をブロックに分割します。例えば、値 \\([1, M]\\) を \\(M/B\\) 個のブロックに分け、各ブロックが担当する値域内の要素数を管理します。
- 各値 \\(v\\) について、その出現回数を直接数える配列 (
counts[v]) を用意します。
挿入操作 (値 \\(v\\) を挿入):
counts[v]をインクリメントし、\\(v\\) が属する値域ブロックの合計カウントもインクリメントします。\\(O(1)\\) で完了します。
k番目要素クエリ:
- まず、どの値域ブロックにk番目の要素が含まれるかを特定します。これは、各値域ブロックの合計カウントを順に加算していき、kを超える最初のブロックを見つけることで行います。これは \\(O(M/B)\\) の操作です。
- k番目の要素が含まれるブロックが見つかったら、そのブロック内の各値のカウント (
counts[v]) を順に調べて、実際にk番目の値が何かを特定します。これは \\(O(B)\\) の操作です。
計算量: 挿入は \\(O(1)\\) です。クエリは \\(O(M/B + B)\\) となり、\\(B = \\sqrt{M}\\) とすると \\(O(\\sqrt{M})\\) になります。 元問題の \\(O(1)\\) クエリは、グローバルなk番目要素クエリにおいては一般的な計算量ではありません。特定の状況（例えば、k番目要素が特定のブロックに存在することが事前に分かっている場合など）を指している可能性があります。
問題4: 値域が大きい場合の単一点挿入とグローバルなk番目要素クエリ
値域が非常に大きい場合、値域に基づくブロック分割はメモリ効率が悪くなります。代わりに、実際に挿入されたデータの集合に対してブロック分割を適用します。
データ構造:
- 実際に挿入された数値を、昇順にソートされた状態を保つように複数のブロックに分割します。各ブロックはだいたい \\(B = \\sqrt{N}\\) 個の要素を保持します（\\(N\\) は現在の要素数）。
- 各ブロックは、要素の配列と、そのブロックが含む要素の最小値/最大値を保持します。
挿入操作 (値 \\(v\\) を挿入):
- 挿入される値 \\(v\\) がどのブロックに属するかを特定します。これは、ブロックの境界値を調べて \\(O(N/B)\\) で行えます。
- 見つけたブロック内に \\(v\\) を挿入し、ブロック内の要素をソートされた状態に保ちます。これは \\(O(B)\\) の操作です。
- もしブロックのサイズが閾値（例: \\(B\\)）を超過した場合、ブロックを分割し、一部の要素を次のブロックに移動させます。この移動が連鎖的に次のブロックへと影響を及ぼす可能性があります。慎重に実装することで、償却 \\(O(\\sqrt{N})\\) で処理できます。
k番目要素クエリ:
- 各ブロックの要素数を順に合計していき、k番目の要素が含まれるブロックを特定します。これは \\(O(N/B)\\) の操作です。
- 見つかったブロック内のソート済み配列から、直接k番目の要素（ブロック内での相対インデックス）を取得します。これは \\(O(1)\\) の操作です。
計算量: 挿入、クエリともに償却 \\(O(N/B + B)\\) であり、\\(B = \\sqrt{N}\\) とすることで \\(O(\\sqrt{N})\\) になります。
問題5: 区間加算と区間内の条件を満たす要素数クエリ (POJ P2801 教主的魔法に類似)
区間内の全要素に値を加算し、指定された区間内で特定の値 \\(C\\) 以上である要素の数を数える問題です。
データ構造:
- 配列をブロックに分割します。各ブロックは約 \\(B\\) 個の要素を持ちます。
- 各ブロックの要素は、常に昇順にソートされた状態を保ちます。
- 各ブロックに遅延加算値 (
lazyAdd) を保持します。
更新操作 (区間 \\([L, R]\\) に \\(V\\) を加算):
- 区間の両端を含む部分ブロックについて:
- まず、ブロックの
lazyAddを個々の要素に反映し、lazyAddをクリアします。 - 区間内の該当要素に \\(V\\) を直接加算します。
- ブロックの要素を再ソートします。ただし、部分的に変更された要素と未変更の要素をマージすることで、ソートにかかる時間を \\(O(B)\\) に抑えることができます。
- まず、ブロックの
- 区間内に完全に含まれる完全ブロックについて:
- 当該ブロックの
lazyAddに \\(V\\) を加算します。
- 当該ブロックの
要素数クエリ (区間 \\([L, R]\\) で \\(\\geq C\\) となる要素数を計算):
- 区間の両端を含む部分ブロックについて:
- 当該ブロックの
lazyAddを個々の要素に反映し、lazyAddをクリアします。 - 区間内の該当要素を直接走査し、条件を満たす数を数えます。
- 当該ブロックの
- 区間内に完全に含まれる完全ブロックについて:
- 検索値 \\(C\\) からブロックの
lazyAddを差し引いた値 \\(C' = C - lazyAdd\\) を使って、ソート済みのブロック内で二分探索を行います。\\(C'\\) 以上となる最初の要素を見つけ、それ以降の要素が全て条件を満たすと判断します。これにより、\\(O(\\log B)\\) でカウントできます。
- 検索値 \\(C\\) からブロックの
計算量: 更新は \\(O(B + N/B)\\) 、クエリは \\(O(B + N/B \\log B)\\) となります。全体の計算量は \\(O(Q(B + N/B \\log B))\\) です。 最適なブロックサイズ \\(B\\) は \\(\\sqrt{N \\log N}\\) 付近となり、この場合 \\(O(Q\\sqrt{N \\log N})\\) で処理できます。これは \\(N=10^6, Q=3000\\) の制約に対して十分高速です。
以下に、この問題に対応するC++コード例を示します。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // For std::sort, std::min, std::max
#include <cstdio> // For scanf, printf
// 高速入力関数
void fast_read(int& val) {
val = 0;
char c = getchar();
bool neg = false;
while (c < '0' || c > '9') {
if (c == '-') neg = true;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = val * 10 + (c - '0');
c = getchar();
}
if (neg) val = -val;
}
const int MAX_N = 1000005;
const int MAX_BLOCKS = 1005;
int initial_values[MAX_N]; // 元の配列の要素 (a in original)
int sorted_indices[MAX_N]; // 各ブロック内で要素のインデックスをソート (b in original)
int block_start_idx[MAX_BLOCKS]; // 各ブロックの開始インデックス (L in original)
int block_end_idx[MAX_BLOCKS]; // 各ブロックの終了インデックス (R in original)
int block_id[MAX_N]; // 各要素が属するブロックのID (bl in original)
long long block_lazy_add[MAX_BLOCKS]; // 各ブロックの遅延加算値 (tag in original)
int temp_modified_indices[MAX_N]; // 変更された要素のインデックス (c in original)
int temp_unmodified_indices[MAX_N]; // 変更されなかった要素のインデックス (d in original)
int temp_merged_indices[MAX_N]; // マージ結果のインデックス (f in original)
int num_array_elements; // N
int num_queries; // QQ
int block_size; // B
int num_blocks; // C (num_blocks in original)
// 要素の値を比較するための関数オブジェクトまたはラムダ
struct ValueComparator {
bool operator()(int idx1, int idx2) const {
return initial_values[idx1] < initial_values[idx2];
}
};
// ブロックのlazy tagを展開し、個々の要素に適用する
void spread_lazy_tag(int block_idx) {
if (block_lazy_add[block_idx] == 0) return;
for (int i = block_start_idx[block_idx]; i <= block_end_idx[block_idx]; ++i) {
initial_values[sorted_indices[i]] += block_lazy_add[block_idx];
}
block_lazy_add[block_idx] = 0;
}
// 部分的に変更されたブロックを再構築し、ソート状態を保つ
void rebuild_block(int block_idx, int range_l, int range_r, int add_val) {
spread_lazy_tag(block_idx); // lazy tagを現在の値に適用
int modified_count = 0;
int unmodified_count = 0;
// 変更範囲内の要素とそれ以外の要素を分離
for (int i = block_start_idx[block_idx]; i <= block_end_idx[block_idx]; ++i) {
int original_idx = sorted_indices[i]; // 元の配列でのインデックス
if (range_l <= original_idx && original_idx <= range_r) {
// 変更範囲内の要素
initial_values[original_idx] += add_val;
temp_modified_indices[modified_count++] = original_idx;
} else {
// 変更範囲外の要素
temp_unmodified_indices[unmodified_count++] = original_idx;
}
}
// 分離した要素をマージしてソート状態を再構築
int p_modified = 0;
int p_unmodified = 0;
int p_merged = 0;
while (p_modified < modified_count && p_unmodified < unmodified_count) {
if (initial_values[temp_modified_indices[p_modified]] < initial_values[temp_unmodified_indices[p_unmodified]]) {
temp_merged_indices[p_merged++] = temp_modified_indices[p_modified++];
} else {
temp_merged_indices[p_merged++] = temp_unmodified_indices[p_unmodified++];
}
}
while (p_modified < modified_count) {
temp_merged_indices[p_merged++] = temp_modified_indices[p_modified++];
}
while (p_unmodified < unmodified_count) {
temp_merged_indices[p_merged++] = temp_unmodified_indices[p_unmodified++];
}
// 再構築されたインデックスをブロックに格納
for (int i = 0; i < p_merged; ++i) {
sorted_indices[block_start_idx[block_idx] + i] = temp_merged_indices[i];
}
}
// 区間加算操作
void update_range(int query_l, int query_r, int add_val) {
int block_l = block_id[query_l];
int block_r = block_id[query_r];
if (block_l == block_r) { // 全て同一ブロック内
rebuild_block(block_l, query_l, query_r, add_val);
return;
}
// 最初の部分ブロックの処理
rebuild_block(block_l, query_l, block_end_idx[block_l], add_val);
// 中間の完全ブロックの処理
for (int i = block_l + 1; i <= block_r - 1; ++i) {
block_lazy_add[i] += add_val;
// 注意: initial_valuesにはlazy_addが反映されていないので、block_lazy_addのみを更新
}
// 最後の部分ブロックの処理
rebuild_block(block_r, block_start_idx[block_r], query_r, add_val);
}
// 区間内のC以上の要素数クエリ
int query_count_greater_equal(int query_l, int query_r, int threshold) {
int block_l = block_id[query_l];
int block_r = block_id[query_r];
int count = 0;
if (block_l == block_r) { // 全て同一ブロック内
spread_lazy_tag(block_l);
for (int i = query_l; i <= query_r; ++i) {
if (initial_values[i] >= threshold) {
count++;
}
}
return count;
}
// 最初の部分ブロックの処理
spread_lazy_tag(block_l);
for (int i = query_l; i <= block_end_idx[block_l]; ++i) {
if (initial_values[i] >= threshold) {
count++;
}
}
// 中間の完全ブロックの処理 (二分探索を使用)
for (int i = block_l + 1; i <= block_r - 1; ++i) {
long long effective_threshold = threshold - block_lazy_add[i]; // lazy tagを考慮した実効的な閾値
// sorted_indicesはソートされたインデックスを格納
// initial_values[sorted_indices[k]]はk番目の要素の値
// block_start_idx[i]からblock_end_idx[i]の範囲で二分探索
int current_block_start = block_start_idx[i];
int current_block_end = block_end_idx[i];
int lower_bound_pos = -1;
int pl = current_block_start;
int pr = current_block_end;
while (pl <= pr) {
int mid_idx_in_sorted_indices = pl + (pr - pl) / 2;
int actual_array_idx = sorted_indices[mid_idx_in_sorted_indices];
if (initial_values[actual_array_idx] >= effective_threshold) {
lower_bound_pos = mid_idx_in_sorted_indices;
pr = mid_idx_in_sorted_indices - 1;
} else {
pl = mid_idx_in_sorted_indices + 1;
}
}
if (lower_bound_pos != -1) {
count += (current_block_end - lower_bound_pos + 1);
}
}
// 最後の部分ブロックの処理
spread_lazy_tag(block_r);
for (int i = block_start_idx[block_r]; i <= query_r; ++i) {
if (initial_values[i] >= threshold) {
count++;
}
}
return count;
}
int main() {
fast_read(num_array_elements);
fast_read(num_queries);
for (int i = 1; i <= num_array_elements; ++i) {
fast_read(initial_values[i]);
sorted_indices[i] = i; // sorted_indicesは元の配列のインデックスを保持
}
// ブロックサイズの設定
// sqrt(N * log N)が最適な場合が多い
block_size = static_cast<int>(sqrt(num_array_elements * log2(num_array_elements)));
if (block_size == 0) block_size = 1; // 最小ブロックサイズは1
// ブロックの初期化
for (int i = 1; i <= num_array_elements; i += block_size) {
num_blocks++;
block_start_idx[num_blocks] = i;
block_end_idx[num_blocks] = std::min(num_array_elements, i + block_size - 1);
for (int j = block_start_idx[num_blocks]; j <= block_end_idx[num_blocks]; ++j) {
block_id[j] = num_blocks;
}
// 各ブロックの要素をソート (インデックスをソートし、actual_values[index]を比較)
std::sort(sorted_indices + block_start_idx[num_blocks],
sorted_indices + block_end_idx[num_blocks] + 1,
ValueComparator());
}
for (int q = 0; q < num_queries; ++q) {
char operation_type[5];
scanf("%s", operation_type); // "M" for modify, "A" for ask
if (operation_type[0] == 'M') {
int l, r, w;
fast_read(l);
fast_read(r);
fast_read(w);
update_range(l, r, w);
} else { // operation_type[0] == 'A'
int l, r, w;
fast_read(l);
fast_read(r);
fast_read(w);
printf("%d\n", query_count_greater_equal(l, r, w));
}
}
return 0;
}
問題6: 区間加算と区間内のk番目要素クエリ (P5356 由乃打扑克に類似)
指定された区間内の全要素に値を加算し、指定された区間内でk番目に小さい要素を求める問題です（元の問題では「k番目に大きい」とありますが、実装は「k番目に小さい」要素を見つける形が一般的です）。値域が非常に大きい場合にも対応します。
データ構造と更新操作: 問題5と同様に、配列をブロックに分割し、各ブロックをソート済みで遅延加算値を持つようにします。更新操作も問題5と同一です。
k番目要素クエリ (区間 \\([L, R]\\) のk番目要素を計算):
これは、問題5のクエリを発展させたものです。k番目要素の値を直接見つけるのは難しいので、値に対する二分探索を利用します。
- 外側の二分探索: 答えとなる値 \\(X\\) を、考えられる最小値から最大値の範囲で二分探索します。
- 内側のカウント関数 (
count_less_equal(query_l, query_r, X)): 二分探索中の候補値 \\(X\\) に対して、「指定された区間 \\([L, R]\\) 内で \\(X\\) 以下の要素がいくつあるか」を数える関数を実装します。この関数は問題5のクエリとほぼ同様の方法で実装されます。- 部分ブロックの処理:
lazyAddを展開し、直接要素を走査してカウントします。 - 完全ブロックの処理:
lazyAddを考慮した実効的な閾値 \\(X' = X - lazyAdd\\) を使って、ソート済みブロック内で二分探索を行い、\\(X'\\) 以下の要素数をカウントします。
- 部分ブロックの処理:
- 外側の二分探索では、
count_less_equal(X)の結果が \\(k\\) 以上であれば \\(X\\) が候補になりうる（より小さい値を探す）、そうでなければ \\(X\\) は小さすぎる（より大きい値を探す）というロジックで答えを絞り込みます。
計算量: 更新は \\(O(B + N/B)\\) です。クエリは、外側の二分探索が \\(O(\\log V)\\) (Vは値域の大きさ) かかり、内側のカウント関数が \\(O(B + N/B \\log B)\\) かかるため、合計で \\(O(Q(B + N/B \\log B) \\log V)\\) となります。 この計算量をさらに最適化するため、部分ブロックの要素を一時的に抽出してソートし、完全ブロックと同様に二分探索を行うことで、クエリの内側を \\(O(B + N/B \\log B)\\) のオーダーで処理することが可能です。
最適なブロックサイズ \\(B\\) は \\(\\sqrt{N \\log N \\log V}\\) 付近となりますが、定数倍の兼ね合いで \\(B=700\\) 程度が実測上最速になることが多いです。
以下に、この問題に対応するC++コード例を示します。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // For std::sort, std::min, std::max
#include <cstdio> // For scanf, printf
#include <climits> // For LLONG_MIN, LLONG_MAX
// 高速入力関数
void fast_read(int& val) {
val = 0;
char c = getchar();
bool neg = false;
while (c < '0' || c > '9') {
if (c == '-') neg = true;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = val * 10 + (c - '0');
c = getchar();
}
if (neg) val = -val;
}
const int MAX_N = 100005;
const int MAX_BLOCKS = 200; // B=700なので、N/Bで最大150個程度のブロック
long long current_values[MAX_N]; // 元の配列の要素 (a in original)
int block_sorted_indices[MAX_N]; // 各ブロック内で要素のインデックスをソート (b in original)
int block_start_pos[MAX_BLOCKS]; // 各ブロックの開始インデックス (L in original)
int block_end_pos[MAX_BLOCKS]; // 各ブロックの終了インデックス (R in original)
int element_block_id[MAX_N]; // 各要素が属するブロックのID (bl in original)
long long block_lazy_update[MAX_BLOCKS]; // 各ブロックの遅延加算値 (tag in original)
int temp_modified_part[MAX_N]; // 変更された要素のインデックス (c in original)
int temp_unmodified_part[MAX_N]; // 変更されなかった要素のインデックス (d in original)
int temp_merge_result[MAX_N]; // マージ結果のインデックス (f in original)
int temp_scattered_left[MAX_N]; // 左側の散塊要素 (sl in original)
int temp_scattered_right[MAX_N]; // 右側の散塊要素 (sr in original)
int array_size_n; // n
int num_queries; // Q
int current_block_size; // B
int total_num_blocks; // C
// 要素の値を比較するための関数オブジェクトまたはラムダ
struct ValueComparator {
bool operator()(int idx1, int idx2) const {
return current_values[idx1] < current_values[idx2];
}
};
// ブロックのlazy tagを展開し、個々の要素に適用する
void apply_lazy_tag(int block_idx) {
if (block_lazy_update[block_idx] == 0) return;
for (int i = block_start_pos[block_idx]; i <= block_end_pos[block_idx]; ++i) {
current_values[block_sorted_indices[i]] += block_lazy_update[block_idx];
}
block_lazy_update[block_idx] = 0;
}
// 部分的に変更されたブロックを再構築し、ソート状態を保つ
void rebuild_block_sorted_data(int block_idx, int range_l, int range_r, int add_val) {
apply_lazy_tag(block_idx); // lazy tagを現在の値に適用
int modified_count = 0;
int unmodified_count = 0;
// 変更範囲内の要素とそれ以外の要素を分離
for (int i = block_start_pos[block_idx]; i <= block_end_pos[block_idx]; ++i) {
int original_idx = block_sorted_indices[i]; // 元の配列でのインデックス
if (range_l <= original_idx && original_idx <= range_r) {
// 変更範囲内の要素
current_values[original_idx] += add_val;
temp_modified_part[modified_count++] = original_idx;
} else {
// 変更範囲外の要素
temp_unmodified_part[unmodified_count++] = original_idx;
}
}
// 分離した要素をマージしてソート状態を再構築
int p_modified = 0;
int p_unmodified = 0;
int p_merged = 0;
while (p_modified < modified_count && p_unmodified < unmodified_count) {
if (current_values[temp_modified_part[p_modified]] < current_values[temp_unmodified_part[p_unmodified]]) {
temp_merge_result[p_merged++] = temp_modified_part[p_modified++];
} else {
temp_merge_result[p_merged++] = temp_unmodified_part[p_unmodified++];
}
}
while (p_modified < modified_count) {
temp_merge_result[p_merged++] = temp_modified_part[p_modified++];
}
while (p_unmodified < unmodified_count) {
temp_merge_result[p_merged++] = temp_unmodified_part[p_unmodified++];
}
// 再構築されたインデックスをブロックに格納
for (int i = 0; i < p_merged; ++i) {
block_sorted_indices[block_start_pos[block_idx] + i] = temp_merge_result[i];
}
}
// 区間加算操作
void range_update_add(int query_l, int query_r, int add_val) {
int block_l_id = element_block_id[query_l];
int block_r_id = element_block_id[query_r];
if (block_l_id == block_r_id) { // 全て同一ブロック内
rebuild_block_sorted_data(block_l_id, query_l, query_r, add_val);
return;
}
// 最初の部分ブロックの処理
rebuild_block_sorted_data(block_l_id, query_l, block_end_pos[block_l_id], add_val);
// 中間の完全ブロックの処理
for (int i = block_l_id + 1; i <= block_r_id - 1; ++i) {
block_lazy_update[i] += add_val;
}
// 最後の部分ブロックの処理
rebuild_block_sorted_data(block_r_id, block_start_pos[block_r_id], query_r, add_val);
}
// ソート済み配列(インデックス)の中から、閾値k以下の要素数を返す (二分探索)
int count_elements_less_equal(int sorted_idx_array[], int count, long long threshold_val) {
int low = 0, high = count - 1;
int res = -1; // -1 means no element <= threshold_val
while(low <= high) {
int mid = low + (high - low) / 2;
if (current_values[sorted_idx_array[mid]] <= threshold_val) {
res = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return res + 1; // Return count (0-indexed res + 1)
}
// 区間内のX以下の要素数をカウントするヘルパー関数
int count_range_less_equal(int query_l, int query_r, long long target_val) {
int block_l_id = element_block_id[query_l];
int block_r_id = element_block_id[query_r];
int current_count = 0;
int scattered_left_count = 0;
int scattered_right_count = 0;
if (block_l_id == block_r_id) { // 全て同一ブロック内
apply_lazy_tag(block_l_id);
for (int i = query_l; i <= query_r; ++i) {
if (current_values[i] <= target_val) {
current_count++;
}
}
return current_count;
}
// 最初の部分ブロックの処理 (temp_scattered_leftに収集)
apply_lazy_tag(block_l_id);
for (int i = block_start_pos[block_l_id]; i <= block_end_pos[block_l_id]; ++i) {
int original_idx = block_sorted_indices[i];
if (original_idx >= query_l) { // クエリ範囲内
temp_scattered_left[scattered_left_count++] = original_idx;
}
}
// temp_scattered_leftは元のブロックがソートされているのでそのままソート済み
current_count += count_elements_less_equal(temp_scattered_left, scattered_left_count, target_val);
// 中間の完全ブロックの処理 (二分探索を使用)
for (int i = block_l_id + 1; i <= block_r_id - 1; ++i) {
long long effective_threshold = target_val - block_lazy_update[i];
current_count += count_elements_less_equal(block_sorted_indices + block_start_pos[i],
block_end_pos[i] - block_start_pos[i] + 1,
effective_threshold);
}
// 最後の部分ブロックの処理 (temp_scattered_rightに収集)
apply_lazy_tag(block_r_id);
for (int i = block_start_pos[block_r_id]; i <= block_end_pos[block_r_id]; ++i) {
int original_idx = block_sorted_indices[i];
if (original_idx <= query_r) { // クエリ範囲内
temp_scattered_right[scattered_right_count++] = original_idx;
}
}
// temp_scattered_rightは元のブロックがソートされているのでそのままソート済み
current_count += count_elements_less_equal(temp_scattered_right, scattered_right_count, target_val);
return current_count;
}
// 区間内のk番目要素クエリ (k-th smallest)
long long query_kth_element(int query_l, int query_r, int k) {
if (k < 1 || k > (query_r - query_l + 1)) return LLONG_MIN; // 無効なk
long long low_val = -2e9 - 7; // 最小可能値
long long high_val = 2e9 + 7; // 最大可能値
long long ans_val = high_val; // 結果を保持 (k番目の要素の最小値)
// 二分探索でk番目の値を特定
while (low_val <= high_val) {
long long mid_val = low_val + (high_val - low_val) / 2;
if (count_range_less_equal(query_l, query_r, mid_val) >= k) {
ans_val = mid_val;
high_val = mid_val - 1;
} else {
low_val = mid_val + 1;
}
}
return ans_val;
}
int main() {
fast_read(array_size_n);
fast_read(num_queries);
for (int i = 1; i <= array_size_n; ++i) {
int val;
fast_read(val);
current_values[i] = val;
block_sorted_indices[i] = i; // sorted_indicesは元の配列のインデックスを保持
}
// ブロックサイズの設定
current_block_size = 700;
// ブロックの初期化
for (int i = 1; i <= array_size_n; i += current_block_size) {
total_num_blocks++;
block_start_pos[total_num_blocks] = i;
block_end_pos[total_num_blocks] = std::min(array_size_n, i + current_block_size - 1);
for (int j = block_start_pos[total_num_blocks]; j <= block_end_pos[total_num_blocks]; ++j) {
element_block_id[j] = total_num_blocks;
}
// 各ブロックの要素をソート (インデックスをソートし、actual_values[index]を比較)
std::sort(block_sorted_indices + block_start_pos[total_num_blocks],
block_sorted_indices + block_end_pos[total_num_blocks] + 1,
ValueComparator());
}
while (num_queries--) {
int op_type, l, r, w;
fast_read(op_type);
fast_read(l);
fast_read(r);
fast_read(w);
if (op_type == 1) { // クエリタイプ1: k番目要素
long long result = query_kth_element(l, r, w);
printf("%lld\n", result);
} else { // クエリタイプ2: 区間加算
range_update_add(l, r, w);
}
}
return 0;
}
問題7: 2次元平面における区間加算と点クエリ (P3863 序列に類似)
配列の区間加算と、ある位置 (インデックス) における特定時刻以前の値が \\(\\geq k\\) である回数を問い合わせる問題です。
2次元変換とスイープライン法: この問題は、序列軸 (x軸) と時間軸 (y軸) を持つ2次元平面上の問題として捉えることができます。
- 初期値: 配列の初期値 \\(A_i\\) は、位置 \\(i\\) で時刻 \\(0\\) に \\(A_i\\) が加算されたイベントとして扱えます。
- 区間加算: 区間 \\([L, R]\\) に時刻 \\(T\\) で \\(X\\) を加算する操作は、位置 \\(L\\) で時刻 \\(T\\) に \\(+X\\) を、位置 \\(R+1\\) で時刻 \\(T\\) に \\(-X\\) を加えるイベントとして表現できます（差分更新のテクニック）。これにより、矩形領域への加算をエッジイベントに変換します。
- クエリ: 位置 \\(X\\) で時刻 \\(T\\) までの、値が \\(\\geq K\\) である回数を問い合わせるクエリは、位置 \\(X\\) において時刻 \\(0\\) から \\(T\\) までの累積値が \\(\\geq K\\) となる区間の数を問うイベントとして扱えます。
これらのイベントをx座標 (位置) でソートし、x座標が小さい方から順に処理していくスイープライン法を適用します。スイープラインが移動する際、y軸（時間軸）上のデータ構造を更新・クエリします。
y軸上のデータ構造: スイープラインがx軸に沿って移動する際、y軸上の各時刻における値（現在の累積加算値）を管理するデータ構造が必要です。このデータ構造は、以下の2種類の操作を効率的にサポートしなければなりません。
- 時刻区間加算: ある時刻 \\(T_s\\) から最大時刻 \\(M\\) までの全ての時刻に値を加算する。これはy軸上の区間加算です。
- 時刻区間内の要素数クエリ: 時刻 \\(0\\) からある時刻 \\(T_e\\) までの間で、値が \\(\\geq K\\) である時刻の数を数える。これはy軸上の区間クエリです。
これらの要件は、まさに問題5の「区間加算と区間内の条件を満たす要素数クエリ」と一致します。したがって、y軸上のデータ構造としてブロック分割データ構造を再利用できます。
計算量: イベントの総数は初期値 \\(N\\) とクエリ \\(Q\\) の線形倍（通常 \\(O(N+Q)\\) イベント）。各イベント処理でy軸上のデータ構造の操作が行われます。y軸上のデータ構造のサイズは最大時刻 (\\(M\\) もしくは \\(Q\\) ) に依存し、その操作は \\(O(\\sqrt{M \\log M})\\) です。 したがって、全体の計算量は \\(O((N+Q) \\sqrt{M \\log M})\\) となります。
以下に、この問題に対応するC++コード例を示します。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // For std::sort, std::min, std::max
#include <cstdio> // For scanf, printf
#include <map> // For coordinate compression if needed, though not in original
// 高速入力関数
void fast_read(int& val) {
val = 0;
char c = getchar();
bool neg = false;
while (c < '0' || c > '9') {
if (c == '-') neg = true;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = val * 10 + (c - '0');
c = getchar();
}
if (neg) val = -val;
}
const int MAX_N_ARR = 100005; // 配列サイズN
const int MAX_M_TIME = 100005; // 最大時刻M (クエリ数Q)
const int MAX_BLOCKS_TIME = 1005; // MAX_M_TIME / sqrt(MAX_M_TIME * log MAX_M_TIME)
const int MAX_EVENTS = MAX_N_ARR * 6; // 初期値2N + クエリ(タイプ1は2イベント、タイプ2は1イベント)
long long time_series_values[MAX_M_TIME]; // y軸上のデータ構造の「値」配列
int time_series_sorted_indices[MAX_M_TIME]; // y軸データ構造のソート済みインデックス配列
int block_start_time[MAX_BLOCKS_TIME]; // y軸データ構造のブロック開始インデックス
int block_end_time[MAX_BLOCKS_TIME]; // y軸データ構造のブロック終了インデックス
int time_block_id[MAX_M_TIME]; // 各時刻が属するブロックのID
long long time_block_lazy_add[MAX_BLOCKS_TIME]; // y軸データ構造の遅延加算値
int temp_modified_indices_time[MAX_M_TIME];
int temp_unmodified_indices_time[MAX_M_TIME];
int temp_merged_indices_time[MAX_M_TIME];
int num_arr_elements_n; // N (配列の長さ)
int num_time_points_m; // M (時刻の最大値, Qとほぼ同じ)
struct Event {
int x_coord; // 序列軸 (位置)
int y_coord_time; // 時間軸 (時刻)
int event_id; // クエリID (0は更新イベント)
int value_change; // 加算値または閾値
bool operator<(const Event& other) const {
if (x_coord != other.x_coord) return x_coord < other.x_coord;
if (y_coord_time != other.y_coord_time) return y_coord_time < other.y_coord_time;
// 更新イベントをクエリイベントより先に処理するため、idで優先順位
// id=0 (更新) を id>0 (クエリ) より優先
return event_id < other.event_id;
}
};
Event events[MAX_EVENTS];
int total_events_count;
int query_results[MAX_M_TIME]; // クエリ結果を保存
int query_types[MAX_M_TIME]; // クエリタイプを保存 (元のop配列)
int time_block_size;
int total_time_blocks;
// y軸上のデータ構造: 要素の値を比較するための関数オブジェクト
struct TimeValueComparator {
bool operator()(int idx1, int idx2) const {
return time_series_values[idx1] < time_series_values[idx2];
}
};
// y軸データ構造のlazy tagを展開
void spread_time_block_lazy_tag(int block_idx) {
if (time_block_lazy_add[block_idx] == 0) return;
for (int i = block_start_time[block_idx]; i <= block_end_time[block_idx]; ++i) {
time_series_values[time_series_sorted_indices[i]] += time_block_lazy_add[block_idx];
}
time_block_lazy_add[block_idx] = 0;
}
// y軸データ構造の部分ブロックを再構築
void rebuild_time_block(int block_idx, int range_l_time, int range_r_time, int add_val) {
spread_time_block_lazy_tag(block_idx);
int modified_count = 0;
int unmodified_count = 0;
// 変更範囲内の時刻とそれ以外の時刻を分離
for (int i = block_start_time[block_idx]; i <= block_end_time[block_idx]; ++i) {
int original_time_idx = time_series_sorted_indices[i];
if (range_l_time <= original_time_idx && original_time_idx <= range_r_time) {
time_series_values[original_time_idx] += add_val;
temp_modified_indices_time[modified_count++] = original_time_idx;
} else {
temp_unmodified_indices_time[unmodified_count++] = original_time_idx;
}
}
int p_modified = 0, p_unmodified = 0, p_merged = 0;
while (p_modified < modified_count && p_unmodified < unmodified_count) {
if (time_series_values[temp_modified_indices_time[p_modified]] < time_series_values[temp_unmodified_indices_time[p_unmodified]]) {
temp_merged_indices_time[p_merged++] = temp_modified_indices_time[p_modified++];
} else {
temp_merged_indices_time[p_merged++] = temp_unmodified_indices_time[p_unmodified++];
}
}
while (p_modified < modified_count) temp_merged_indices_time[p_merged++] = temp_modified_indices_time[p_modified++];
while (p_unmodified < unmodified_count) temp_merged_indices_time[p_merged++] = temp_unmodified_indices_time[p_unmodified++];
for (int i = 0; i < p_merged; ++i) {
time_series_sorted_indices[block_start_time[block_idx] + i] = temp_merged_indices_time[i];
}
}
// y軸データ構造の区間加算 (時刻 from_time から最大時刻まで)
void update_time_range_from(int from_time, int add_val) {
int block_id_from = time_block_id[from_time];
// 最初の部分ブロックを処理
// from_time から block_end_time[block_id_from] まで
rebuild_time_block(block_id_from, from_time, block_end_time[block_id_from], add_val);
// 残りの完全ブロックを処理 (lazy tag)
for (int i = block_id_from + 1; i <= total_time_blocks; ++i) {
time_block_lazy_add[i] += add_val;
}
}
// y軸データ構造の区間クエリ (時刻 0 から up_to_time までで、値が threshold 以上となる要素数をカウント)
int query_time_range_count_greater_equal(int up_to_time, int threshold) {
int block_id_up_to = time_block_id[up_to_time];
int count = 0;
// 最初のブロックから、クエリ範囲のブロック直前まで
for (int i = 1; i < block_id_up_to; ++i) {
long long effective_threshold = threshold - time_block_lazy_add[i];
int block_curr_start = block_start_time[i];
int block_curr_end = block_end_time[i];
int lower_bound_pos = -1;
int pl = block_curr_start;
int pr = block_curr_end;
while (pl <= pr) {
int mid_idx = pl + (pr - pl) / 2;
int actual_time_idx = time_series_sorted_indices[mid_idx];
if (time_series_values[actual_time_idx] >= effective_threshold) {
lower_bound_pos = mid_idx;
pr = mid_idx - 1;
} else {
pl = mid_idx + 1;
}
}
if (lower_bound_pos != -1) {
count += (block_curr_end - lower_bound_pos + 1);
}
}
// クエリ範囲を含むブロックを処理
spread_time_block_lazy_tag(block_id_up_to);
for (int i = block_start_time[block_id_up_to]; i <= up_to_time; ++i) {
if (time_series_values[i] >= threshold) {
count++;
}
}
return count;
}
int main() {
fast_read(num_arr_elements_n);
fast_read(num_time_points_m); // Mは最大時刻、ここではクエリ数とみなす
// 初期値のイベントを追加 (時刻0での加算)
for (int i = 1; i <= num_arr_elements_n; ++i) {
int x_val; fast_read(x_val);
events[++total_events_count] = {i, 0, 0, x_val}; // id=0は更新イベント
events[++total_events_count] = {i + 1, 0, 0, -x_val}; // 差分法
}
// y軸データ構造の初期設定 (時刻0からMまでを対象)
// sorted_indicesは0からMまでをカバー
for (int i = 0; i <= num_time_points_m; ++i) {
time_series_sorted_indices[i] = i; // 時刻インデックスをそのまま格納
}
// ブロックサイズの設定 (sqrt(M * log M)が最適)
// log2(0)は未定義なので、Mが小さい場合は分岐
double log_val = (num_time_points_m > 1) ? log2(num_time_points_m) : 0;
time_block_size = static_cast<int>(sqrt(num_time_points_m * log_val));
if (time_block_size == 0) time_block_size = 1;
// y軸データ構造のブロック初期化
for (int i = 0; i <= num_time_points_m; i += time_block_size) {
total_time_blocks++;
block_start_time[total_time_blocks] = i;
block_end_time[total_time_blocks] = std::min(num_time_points_m, i + time_block_size - 1);
for (int j = block_start_time[total_time_blocks]; j <= block_end_time[total_time_blocks]; ++j) {
time_block_id[j] = total_time_blocks;
}
// y軸ブロックの要素をソート (インデックスをソート)
// 初期値は全て0なのでソートしても順序は変わらないが、形式的に
std::sort(time_series_sorted_indices + block_start_time[total_time_blocks],
time_series_sorted_indices + block_end_time[total_time_blocks] + 1,
TimeValueComparator());
}
// クエリイベントの追加
for (int i = 1; i <= num_time_points_m; ++i) { // Mはクエリの総数
fast_read(query_types[i]); // op配列をここで読み込む
if (query_types[i] == 1) { // タイプ1: 区間更新
int l, r, x_val;
fast_read(l); fast_read(r); fast_read(x_val);
events[++total_events_count] = {l, i, 0, x_val}; // 開始位置で加算
events[++total_events_count] = {r + 1, i, 0, -x_val}; // 終了位置+1で減算
} else { // タイプ2: クエリ
int x, y; // x=位置, y=閾値 (yは元コードのwに相当するが、ここではy_coord_timeと閾値を区別するため)
fast_read(x); fast_read(y);
events[++total_events_count] = {x, i - 1, i, y}; // id=iはクエリID
}
}
// 全てのイベントをx座標、y座標、idの順でソート
std::sort(events + 1, events + total_events_count + 1);
// スイープライン処理
for (int i = 1; i <= total_events_count; ++i) {
if (events[i].event_id == 0) { // 更新イベント (id=0)
update_time_range_from(events[i].y_coord_time, events[i].value_change);
} else { // クエリイベント (id > 0)
query_results[events[i].event_id] = query_time_range_count_greater_equal(events[i].y_coord_time, events[i].value_change);
}
}
// クエリ結果の出力
for (int i = 1; i <= num_time_points_m; ++i) {
if (query_types[i] == 2) { // タイプ2クエリのみ出力
printf("%d\n", query_results[i]);
}
}
return 0;
}