数列分块技術の入門と問題解説
数列分块入门 1
長さ n の数列を管理し、区間加算と単一点クエリを行う。
解法
ブロックサイズを sqrt(n) に設定し、各ブロックに対して遅延評価を使用する。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000 + 1, SQR = 231;
int a[MAXN], bel[MAXN];
int tag[SQR], lp[SQR], rp[SQR];
void updateBlock(int l, int r, int val) {
...
7月7日 18:04 投稿
主要アルゴリズムとデータ構造の実践: セグメントツリー、ハンガリー法、素因数分解Union-Find
競技プログラミング問題解決のヒント
競技プログラミングでは、時間計算量の制約をクリアするために効率的なアルゴリズムやデータ構造の理解が不可欠です。以下に、いくつかの実践的なアプローチとコード例を紹介します。
繰り返しの多いクエリに対する前計算（累積和）
多数のクエリに対して同じ計算を繰り返す場合、事前に結果を前計算しておくことで、各クエリの処理時 ...
6月21日 22:28 投稿
線分木を使用した複雑な操作の実装
この問題では以下の4つの操作を実装する必要があります：
操作1: 結果にaを加算
操作2: 結果からaを減算
操作3: 結果にaを乗算
操作4: 結果にa * Xを加算
これらの操作を効率的に処理するために、線分木を使用します。線分木は区間最大値と最小値、加算の遅延評価タグ、乗算の遅延評価タグ、代入の遅延評価タグ、および操作4用の遅延評価タグを管理します。
木の構築
通 ...
6月12日 18:13 投稿