题解：P13977 数列分块入门 2

xAlec · 2025-09-06 16:35:47 · 题解

Solution

区间加法，询问区间内小于某个值 x 的元素个数。

设块长为 T，依旧是考虑散块暴力统计，整块考虑二分，但是显然我们需要时刻保持数组有序。

对于修改散块的情况，本质上是修改了某个整块的一部分，所以我们需要对其所属整块进行重新排序，复杂度 O(T\log T)。

对于整块，依旧是打加法标记，我们一开始就将所有整块排序再打加法标记不会影响块内顺序，复杂度 O(\frac{n}{T}\log T)。

这样看来总复杂度就是 O(n(T\log T + \frac{n}{T}\log T))，在 T = \sqrt{n} 时取得最小值，此时复杂度 O(n\sqrt{n}\cdot\log{n})。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MAXN = 2e5 + 10;
int n, A[MAXN], blk[MAXN], L[MAXN], R[MAXN], maxblk, siz, tag[MAXN];
vector<int> val[MAXN];

inline void pushup (int pos) {
    val[pos].clear();
    for (int i = L[pos]; i <= R[pos]; i ++) 
        val[pos].push_back (A[i]);
    sort (val[pos].begin(), val[pos].end());
}

inline void Modify (int l, int r, int k) {
    int lpos = blk[l], rpos = blk[r];
    if (lpos == rpos) {
        for (int i = l; i <= r; i ++) A[i] += k;
        pushup (lpos);
    } else {
        for (int i = l; i <= R[lpos]; i ++) A[i] += k;
        for (int i = L[rpos]; i <= r; i ++) A[i] += k;
        pushup (lpos), pushup (rpos);
        for (int i = lpos + 1; i <= rpos - 1; i ++) tag[i] += k;
    }
}

inline int Query (int l, int r, int k) {
    int lpos = blk[l], rpos = blk[r], tot = 0;
    if (lpos == rpos) {
        for (int i = l; i <= r; i ++) 
            tot += (A[i] + tag[lpos] < k);
    } else {
        for (int i = l; i <= R[lpos]; i ++) 
            tot += (A[i] + tag[lpos] < k);
        for (int i = L[rpos]; i <= r; i ++)
            tot += (A[i] + tag[rpos] < k);
        for (int i = lpos + 1; i <= rpos - 1; i ++) 
            tot += lower_bound (val[i].begin(), val[i].end(), k - tag[i]) - val[i].begin();
    }
    return tot;
}
// function

signed main() {
    scanf ("%lld", &n);
    siz = sqrt(n);
    for (int i = 1; i <= n; i ++) {
        scanf ("%lld", &A[i]);
        blk[i] = (i - 1) / siz + 1;
        val[blk[i]].push_back (A[i]);
    }
    maxblk = blk[n];
    for (int i = 1; i <= maxblk; i ++) {
        L[i] = (i - 1) * siz + 1;
        R[i] = min (i * siz, n);
        sort (val[i].begin(), val[i].end());
    }
    // readin & preprocess

    int opt = 0, l = 0, r = 0, c = 0;
    for (int i = 1; i <= n; i ++) {
        scanf ("%lld %lld %lld %lld", &opt, &l, &r, &c);
        if (!opt) {
            Modify (l, r, c);
        } else {
            printf ("%lld\n", Query (l, r, c * c));
        }
    }
    // query

    return 0;
}