题解：P13978 数列分块入门 3

xAlec · 2025-09-06 16:44:46 · 题解

Solution

区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

和数列分块入门 2 同一个道理，都是考虑在有序数组上处理问题，代码实现略有不同。

设块长为 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;
constexpr int inf = 0x3f3f3f3f3f3f3f3f;
int n, A[MAXN], opt, l, r, c, blk[MAXN], maxblk, L[MAXN], R[MAXN], siz, tag[MAXN];
struct Value { 
    int pos, val, col; 
    Value (int pos = 0, int val = 0, int col = 0):pos(pos), val(val), col(col){};
    bool operator < (const Value &s) const { return val < s.val; }
} Val[MAXN];

inline void Modify (int l, int r, int c) {
    int lpos = Val[l].col, rpos = Val[r].col;
    if (lpos == rpos) {
        for (int i = L[lpos]; i <= R[lpos]; i ++) {
            if (Val[i].pos >= l && Val[i].pos <= r) Val[i].val += c;
        }
        sort (Val + L[lpos], Val + R[lpos] + 1);
    } else {
        for (int i = L[lpos]; i <= R[lpos]; i ++) {
            if (Val[i].pos >= l) Val[i].val += c;
        }
        sort (Val + L[lpos], Val + R[lpos] + 1);
        for (int i = L[rpos]; i <= R[rpos]; i ++) {
            if (Val[i].pos <= r) Val[i].val += c;
        }
        sort (Val + L[rpos], Val + R[rpos] + 1);
        for (int i = lpos + 1; i <= rpos - 1; i ++) tag[i] += c;
    }
}

inline int Query (int l, int r, int c) {
    int lpos = Val[l].col, rpos = Val[r].col, tot = ~inf;
    if (lpos == rpos) {
        for (int i = L[lpos]; i <= R[lpos]; i ++) {
            if (Val[i].pos >= l && Val[i].pos <= r && Val[i].val + tag[lpos] < c)
                tot = max (tot, Val[i].val + tag[lpos]);
        }
    } else {
        for (int i = L[lpos]; i <= R[lpos]; i ++) {
            if (Val[i].pos >= l && Val[i].val + tag[lpos] < c)
                tot = max (tot, Val[i].val + tag[lpos]);
        }
        for (int i = L[rpos]; i <= R[rpos]; i ++) {
            if (Val[i].pos <= r && Val[i].val + tag[rpos] < c)
                tot = max (tot, Val[i].val + tag[rpos]);
        }
        for (int i = lpos + 1; i <= rpos - 1; i ++) {
            int lp = L[i], rp = R[i], mid = 0, ret = 0;
            while (lp <= rp) {
                mid = (lp + rp) >> 1;
                if (Val[mid].val + tag[i] < c) {
                    ret = mid, lp = mid + 1;
                } else {
                    rp = mid - 1;
                }
            }
            if (ret)
                tot = max (tot, Val[ret].val + tag[i]);
        }
    }
    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[i] = Value (i, A[i], blk[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 + L[i], Val + R[i] + 1);
    }
    // readin()
    for (int i = 1; i <= n; i ++) {
        scanf ("%lld %lld %lld %lld", &opt, &l, &r, &c);
        if (!opt) {
            Modify (l, r, c);
        } else {
            int ans = Query (l, r, c);
            printf ("%lld\n", ans == ~inf ? -1 : ans);
        }
    }
    return 0;
    // query()
}