题解：P13977 数列分块入门 2

· · 题解

思路分析

这类题是直接套上分块就能直接看出怎么做的。

显然我们可以先将整个序列分块，然后考虑整块和散块怎么操作。

先考虑查询。对于散块，我们直接暴力判断就行了，对于整块，我们考虑进行二分。这意味着我们还需要维护一个块的有序版本。这部分是修改操作的散块负责维护的。

再考虑修改操作。对于整块，我们直接打上一个整体加的 tag，对于散块，我们直接将要加的部分加一下，然后重构对应块的有序版本。

不难分析出来时间复杂度是 O(n\sqrt n\log\sqrt n)=O(n\sqrt n\log n) 的。代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a[500005], l[2300], r[2300], b[500005], op, lp, rp, c, lz[2300], v[500005];
inline void init() {
    int sz = sqrt(n * 1.0);
    for (int i = 1; i <= sz; ++i) {
        l[i] = (i - 1) * sz + 1, r[i] = i * sz;
        sort(a + l[i], a + r[i] + 1);
    }
    if (r[sz] < n) {
        sz++; l[sz] = r[sz - 1] + 1, r[sz] = n;
        sort(a + l[sz], a + r[sz] + 1);
    }
    for (int i = 1; i <= sz; ++i)
        for (int j = l[i]; j <= r[i]; ++j)
            b[j] = i;
}
inline void chg() {
    int lt = b[lp], rt = b[rp];
    if (lt == rt) {
        for (int i = lp; i <= rp; ++i) v[i] += c;
        for (int i = l[lt]; i <= r[rt]; ++i) a[i] = v[i];
        sort(a + l[lt], a + r[rt] + 1);
        return;
    }
    for (int i = lt + 1; i < rt; ++i) lz[i] += c;

    for (int i = lp; i <= r[lt]; ++i) v[i] += c;
    for (int i = l[lt]; i <= r[lt]; ++i) a[i] = v[i];
    sort(a + l[lt], a + r[lt] + 1);

    for (int i = l[rt]; i <= rp; ++i) v[i] += c;
    for (int i = l[rt]; i <= r[rt]; ++i) a[i] = v[i];
    sort(a + l[rt], a + r[rt] + 1);
}
inline int que() {
    int lt = b[lp], rt = b[rp], ans = 0; c *= c;
    if (lt == rt) {
        for (int i = lp; i <= rp; ++i)
            ans += (c > (v[i] + lz[lt]));
        return ans;
    }
    for (int i = lp; i <= r[lt]; ++i)
        ans += (c > (v[i] + lz[lt]));
    for (int i = l[rt]; i <= rp; ++i)
        ans += (c > (v[i] + lz[rt]));
    for (int i = lt + 1; i < rt; ++i)
        ans += lower_bound(a + l[i], a + r[i] + 1, c - lz[i]) - a - l[i];
    return ans;
}
signed main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], v[i] = a[i];
    init();
    for (int i = 1; i <= n; ++i) {
        cin >> op >> lp >> rp >> c;
        if (op) cout << que() << endl;
        else chg();
    }
    return 0;
}