数列分块入门 2

LibreOJ-6278-数列分块入门 2

分析

• 区间加法
• 查询区间内小于某个值$x$的元素个数

实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int N = 50010, T = 230;
int n, a[N];
int pos[N], L[T], R[T];
int add[T];
vector<int> b[T];

void initialize () {
    int t = sqrt(n);
    for (int i = 1; i <= t; ++ i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * t;
    }
    if (R[t] < n) {
        ++ t;
        L[t] = R[t - 1] + 1;
        R[t] = n;
    }

    for (int i = 1; i <= t; ++ i) {
        for (int j = L[i]; j <= R[i]; ++ j) {
            pos[j] = i;
            b[i].push_back(a[j]);
        }
        sort(b[i].begin(), b[i].end());
    }
}
void reset (int k) {
    b[k].clear();
    for (int i = L[k]; i <= R[k]; ++ i) b[k].push_back(a[i]);
    sort(b[k].begin(), b[k].end());
}
void modify (int l, int r, int val) { // a[l ~ r] += val
    int x = pos[l], y = pos[r];
    if (x == y) {
        for (int i = l; i <= r; ++ i) a[i] += val;
        reset(x);
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) add[i] += val;
        for (int i = l; i <= R[x]; ++ i) a[i] += val;
        reset(x);
        for (int i = L[y]; i <= r; ++ i) a[i] += val;
        reset(y);
    }
}
int query (int l, int r, int k) {
    int x = pos[l], y = pos[r];
    int res = 0;
    if (x == y) {
        for (int i = l; i <= r; ++ i)
            if (a[i] + add[x] < k)
                ++ res;
    } else {
        for (int i = x + 1; i <= y - 1; ++ i)
            res += lower_bound(b[i].begin(), b[i].end(), k - add[i]) - b[i].begin();
        for (int i = l; i <= R[x]; ++ i)
            if (a[i] + add[x] < k)
                ++ res;
        for (int i = L[y]; i <= r; ++ i)
            if (a[i] + add[y] < k)
                ++ res;
    }
    return res;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    initialize();
    for (int i = 1, opt, l, r, c; i <= n; ++ i) {
        cin >> opt >> l >> r >> c;
        if (opt == 0) {
            modify(l, r, c);
        } else {
            cout << query(l, r, c * c) << endl;
        }
    }
    return 0;
}