LOJ数列ブロック入門2

link
考えなければならない問題:

完全なブロックはどのように

を処理します

不完全なブロックが

をどのように処理するか

何かを前処理する必要がある

問題解

前処理

各ブロックについて、このブロック内のすべての値を1つのvectorで保存し、このvectorをソートします.目的は私たちの後ろの二分操作を便利にすることです.

完全なブロックについて

更新:iブロック全体に加算する値をl z[i]lz[i]lz[i]lz[i]で保存します.

クエリー:l o w e r lower lower_b o u n d bound boundこのブロックのc減lz[i]より小さい値の個数をクエリします.もともとこのブロックのすべての数にlz[i]が加算されるからです.

不完全なブロックについて

更新:直接更新し、このブロックに対応するvectorを空にしてから、新しい値を追加します.

クエリー:直接クエリー、注意cより小さいのではなく、c-lz[i]

より小さい

#include 
#define ll long long
using namespace std;
const int maxn = 5e4 + 10;
int a[maxn];
vector<int> k[305];
int n, block, num;
int belong[maxn], l[305], r[305], lz[305];

void init() {
    block = sqrt(n);
    num = n / block + (n % block != 0);

    for (int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1;
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * block + 1;
        r[i] = i * block;
    }
    r[num] = n;

    for (int i = 1; i <= n; i++) {
        k[belong[i]].push_back(a[i]);
    }
    for (int i = 1; i <= num; i++) sort(k[i].begin(), k[i].end());
}
void reset(int p) {
    k[p].clear();
    for (int i = l[p]; i <= r[p]; i++) k[p].push_back(a[i]);
    sort(k[p].begin(), k[p].end());
}
void up(int L, int R, int c) {
    if (belong[L] == belong[R]) {
        for (int i = L; i <= R; i++) a[i] += c;
        reset(belong[L]);
        return;
    }

    for (int i = L; i <= r[belong[L]]; i++) a[i] += c;
    reset(belong[L]);

    for (int i = l[belong[R]]; i <= R; i++) a[i] += c;
    reset(belong[R]);

    for (int i = belong[L] + 1; i < belong[R]; i++) lz[i] += c;
}

int qu(int L, int R, ll c) {
    int ans = 0;
    if (belong[L] == belong[R]) {
        for (int i = L; i <= R; i++)
            if (a[i] + lz[belong[L]] < c)
                ans++;
        return ans;
    }

    for (int i = belong[L] + 1; i < belong[R]; i++) {
        ans += lower_bound(k[i].begin(), k[i].end(), c - lz[i]) - k[i].begin();
    }
    for (int i = L; i <= r[belong[L]]; i++)
        if (a[i] + lz[belong[L]] < c)
            ans++;
    for (int i = l[belong[R]]; i <= R; i++)
        if (a[i] + lz[belong[R]] < c)
            ans++;
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    init();
    for (int i = 1; i <= n; i++) {
        int op, L, R, c;
        cin >> op >> L >> R >> c;
        if (op == 1) {
            cout << qu(L, R, c * c) << '
';
        } else {
            up(L, R, c);
        }
    }
}