数列分块入门 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) {
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; ++i) a[i] += val;
        return;
    }
    for (int i = l; i <= rp[bel[l]]; ++i) a[i] += val;
    for (int i = lp[bel[r]]; i <= r; ++i) a[i] += val;
    for (int i = bel[l] + 1; i <= bel[r] - 1; ++i) tag[i] += val;
}

int main() {
    int n, k;
    cin >> n;
    k = sqrt(n);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= k; ++i) {
        lp[i] = (i - 1) * k + 1;
        rp[i] = i * k;
    }
    rp[k] = n;
    for (int i = 1; i <= k; ++i)
        for (int j = lp[i]; j <= rp[i]; ++j) bel[j] = i;
    
    while (n--) {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;
        if (opt == 0) updateBlock(l, r, c);
        if (opt == 1) cout << a[r] + tag[bel[r]] << endl;
    }
}

数列分块入门 2

長さ n の数列を管理し、区間加算と区間内での k より小さい要素数のカウントを行う。

解法

各ブロックに対してソートされたベクトルを維持し、二分探索でカウントを行う。

#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];
vector<int> f[SQR];

void rebuildBlock(int id) {
    f[id].clear();
    for (int i = lp[id]; i <= rp[id]; ++i) f[id].push_back(a[i]);
    sort(f[id].begin(), f[id>.end());
}

void updateBlock(int l, int r, int val) {
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; ++i) a[i] += val;
        rebuildBlock(bel[l]);
        return;
    }
    for (int i = l; i <= rp[bel[l]]; ++i) a[i] += val;
    rebuildBlock(bel[l]);
    for (int i = lp[bel[r]]; i <= r; ++i) a[i] += val;
    rebuildBlock(bel[r]);
    for (int i = bel[l] + 1; i <= bel[r] - 1; ++i) tag[i] += val;
}

int countLessThanK(int l, int r, int k) {
    int ans = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; ++i) if (a[i] + tag[bel[i]] < k) ++ans;
        return ans;
    }
    for (int i = l; i <= rp[bel[l]]; ++i) if (a[i] + tag[bel[i]] < k) ++ans;
    for (int i = lp[bel[r]]; i <= r; ++i) if (a[i] + tag[bel[i]] < k) ++ans;
    for (int i = bel[l] + 1; i <= bel[r] - 1; ++i) 
        ans += lower_bound(f[i].begin(), f[i].end(), k - tag[i]) - f[i].begin();
    return ans;
}

int main() {
    int n, k;
    cin >> n;
    k = sqrt(n);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= k; ++i) {
        lp[i] = (i - 1) * k + 1;
        rp[i] = i * k;
    }
    rp[k] = n;
    for (int i = 1; i <= k; ++i) {
        for (int j = lp[i]; j <= rp[i]; ++j) bel[j] = i;
        rebuildBlock(i);
    }

    while (n--) {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;
        if (opt == 0) updateBlock(l, r, c);
        if (opt == 1) cout << countLessThanK(l, r, c * c) << endl;
    }
}