数列分块技術の入門と問題解説
数列分块入门 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 投稿