题解：P13978 数列分块入门 3

LostKeyToReach · 2025-09-06 12:19:09 · 题解

去年做了这道题开始熟悉分块的。

考虑对序列分块，t_x 表示第 x 块的加法标记。

对于加法操作，直接散块暴力加，整块对 t_x 加上 c。

考虑怎么查询，散块可以直接暴力。但是整块不好维护，因为你要维护满足 a_i + t_x < c 的最大值。但是显而易见地，t_x 相对来说是个定值，那么只要考虑让 a_i 单调就行，于是我们操作前先将所有块排个序，在修改时把散块排序重构掉就行，这样查询时就能二分查找了。

时间复杂度 O(n\sqrt{n}\log\sqrt{n})。

// author : LostKeytoReach
// submitted time : 2024 - 07 - 29 on LibreOJ
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define pb push_back
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef long long ll;
ll n, a[200006];
ll sum[200006], tag[200006];
int id[200006], block, mxn;
vector <ll> p[2000006];
ll find(int x, ll val) {
    int ans = -1, l = 0, r = (int)p[x].size() - 1;

    while (l <= r) {
        int mid = l + r >> 1;

        if (p[x][mid] < val)
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }

    return ans;
}
void reset(int x) {
    p[x].clear();
    int up = (x - 1) * block + 1;

    for (int i = up; id[i] == x; i++) {
        p[x].pb(a[i]);
    }

    sort(all(p[x]));
}
void modify(int l, int r, ll v) {
    int lid = id[l], rid = id[r];

    if (lid == rid) {
        for (int i = l; i <= r; i++) {
            a[i] += v;
        }

        reset(lid);
        return;
    }

    for (int i = l; id[i] == lid; i++) {
        a[i] += v;
    }

    reset(lid);

    for (int i = lid + 1; i < rid; i++) {
        tag[i] += v;
    }

    for (int i = r; id[i] == rid; i--) {
        a[i] += v;
    }

    reset(rid);
}
ll query(int l, int r, ll v) {
    int lid = id[l], rid = id[r];
    ll ans = -1e18;

    if (lid == rid) {
        for (int i = l; i <= r; i++) {
            if (a[i] + tag[lid] < v) {
                ans = max(ans, a[i] + tag[lid]);
            }
        }

        return (ans == -1e18 ? -1 : ans);
    }

    for (int i = l; id[i] == lid; i++) {
        if (a[i] + tag[lid] < v) {
            ans = max(ans, a[i] + tag[lid]);
        }
    }

    for (int i = lid + 1; i < rid; i++) {
        int pos = find(i, v - tag[i]);

        if (pos >= 0) {
            ans = max(ans, p[i][pos] + tag[i]);
        }
    }

    for (int i = r; id[i] == rid; i--) {
        if (a[i] + tag[rid] < v) {
            ans = max(ans, a[i] + tag[rid]);
        }
    }

    return (ans == -1e18 ? -1 : ans);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    block = sqrt(n);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[id[i] = (i - 1) / block + 1] += a[i];
    }

    for (int i = 1; i <= n; i++) {
        p[id[i]].pb(a[i]);
    }

    mxn = *max_element(id + 1, id + n + 1);

    for (int i = 1; i <= mxn; i++)
        sort(all(p[i]));

    for (int lxl = 1; lxl <= n; lxl++) {
        ll o, l, r, x;
        cin >> o >> l >> r >> x;

        if (o == 0) {
            modify(l, r, x);
        } else {
            cout << query(l, r, x) << '\n';
        }
    }
}