LibreOJ6279. 数列分块入门 3 题解

题目描述

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，询问区间内小于某个值 \(x\) 的前驱（比其小的最大元素）。

输入格式

第一行输入一个数字 \(n\)。

第二行输入 \(n\) 个数字，第 \(i\) 个数字为 \(a_i\)，以空格隔开。

接下来输入 \(n\) 行询问，每行输入四个数字 \(opt\)、\(l\)、\(r\)、\(c\)，以空格隔开。

若 \(opt=0\)，表示将位于\([l,r]\) 之间的数字都加 \(c\)。

若 \(opt=1\)，表示询问 \([l,r]\) 中 \(c\) 的前驱的值（不存在则输出 \(-1\)）。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例输入

样例输出

3

-1

数据范围与提示

对于 \(100%\) 的数据，\(1 \le n \le 100000, -2^{31} \le others,ans \le 2^{31}-1\)。

解题思路

本题和《数列分块入门 2》思路类似，同样是开一个数组 \(b\) 并块内排序，同样是二分找 \(\le c\) 的最大值。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

int n, m, a[maxn], b[maxn], p[maxn], v[400], op, l, r, c;

inline void chk_max(int &a, int b) {

    if (b == -1) return;

    if (a == -1 || a < b) a = b;

}

void update_part(int pid) {

    int i1 = (pid-1)*m+1, i2 = min(pid*m+1, n+1);   // 注意边界条件

    for (int i = i1; i < i2; i ++)

        b[i] = a[i];

    sort(b+i1, b+i2);

}

void add(int l, int r, int c) {

    if (p[l] == p[r]) { // 说明在同一个分块，直接更新

        for (int i = l; i <= r; i ++) a[i] += c;

        update_part(p[l]);

        return;

    }

    if (l % m != 1) {    // 说明l不是分块p[l]的第一个元素

        for (int i = l; p[i]==p[l]; i ++) {

            a[i] += c;

        }

        update_part(p[l]);

    }

    else v[p[l]] += c;

    if (r % m != 0) { // 说明r不是分块p[r]的最后一个元素

        for (int i = r; p[i]==p[r]; i --)

            a[i] += c;

        update_part(p[r]);

    }

    else v[p[r]] += c;

    for (int i = p[l]+1; i < p[r]; i ++)

        v[i] += c;

}

int pre_part(int pid, int c) {

    int i1 = (pid-1)*m+1, i2 = min(pid*m+1, n+1);

    int id = lower_bound(b+i1, b+i2, c-v[pid]) - (b+i1);

    if (id == 0) return -1;

    return b[i1+id-1]+v[pid];

}

int get_pre(int l, int r, int c) {

    int res = -1;

    if (p[l] == p[r]) { // 说明在同一个分块，直接更新

        for (int i = l; i <= r; i ++)

            if (a[i]+v[p[i]] < c)

                chk_max(res, a[i]+v[p[i]]);

        return res;

    }

    if (l % m != 1) {    // 说明l不是分块p[l]的第一个元素

        for (int i = l; p[i]==p[l]; i ++)

            if (a[i]+v[p[i]] < c)

                chk_max(res, a[i]+v[p[i]]);

    }

    else chk_max(res, pre_part(p[l], c));

    if (r % m != 0) { // 说明r不是分块p[r]的最后一个元素

        for (int i = r; p[i]==p[r]; i --)

            if (a[i]+v[p[i]] < c)

                chk_max(res, a[i]+v[p[i]]);

    }

    else chk_max(res, pre_part(p[r], c));

    for (int i = p[l]+1; i < p[r]; i ++)

        chk_max(res, pre_part(i, c));

    return res;

}

int main() {

    scanf("%d", &n);

    m = sqrt(n);

    for (int i = 1; i <= n; i ++) p[i] = (i-1)/m + 1;

    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i += m) update_part(p[i]);  // 初始化

    for (int i = 0; i < n; i ++) {

        scanf("%d%d%d%d", &op, &l, &r, &c);

        if (op == 0) add(l, r, c);

        else printf("%d\n", get_pre(l, r, c));

    }

    return 0;

}

巴特西