数列分块入门 3

LibreOJ-6279-数列分块入门 3

分析

• 区间加法
• 查询区间内小于某个值$x$的前驱（比其小的最大元素）

实现

#include <iostream>
#include <set>
#include <cmath>
using namespace std;

const int N = 100010, T = 320;
int n, a[N];
int pos[N], L[T], R[T];
int add[T];
set<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].insert(a[j]);
        }
    }
}
void modify (int l, int r, int val) {
    int x = pos[l], y = pos[r];
    if (x == y) {
        for (int i = l; i <= r; ++ i) {
            b[x].erase(a[i]);
            a[i] += val;
            b[x].insert(a[i]);
        }
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) add[i] += val;
        for (int i = l; i <= R[x]; ++ i) {
            b[x].erase(a[i]);
            a[i] += val;
            b[x].insert(a[i]);
        }
        for (int i = L[y]; i <= r; ++ i) {
            b[y].erase(a[i]);
            a[i] += val;
            b[y].insert(a[i]);
        }
    }
}
int query (int l, int r, int val) {
    int x = pos[l], y = pos[r];
    int res = -1;
    if (x == y) {
        for (int i = l; i <= r; ++ i)
            if (a[i] + add[x] < val)
                res = max(res, a[i] + add[x]);
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) {
            auto ptr = b[i].lower_bound(val - add[i]);
            if (ptr == b[i].begin()) continue;
            res = max(res, *(-- ptr) + add[i]);
        }
        for (int i = l; i <= R[x]; ++ i)
            if (a[i] + add[x] < val)
                res = max(res, a[i] + add[x]);
        for (int i = L[y]; i <= r; ++ i)
            if (a[i] + add[y] < val)
                res = max(res, a[i] + add[y]);
    }
    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) << endl;
        }
    }
    return 0;
}