题目链接
题目描述
给定一个长度为 的数组
，你需要构建一个数据结构来支持以下两种操作共
次：
- 区间增量：给定区间
和一个整数
，将该区间中的所有元素
修改为
。
- 区间前驱：给定区间
，查询该区间中所有小于
数据范围：,
。
解题思路
本题涉及区间修改和一种特殊的区间查询（前驱查询）。标准的线段树可以轻松处理区间增量（通过懒标记），但难以高效地回答区间前驱查询，因为这需要在区间的子集内进行条件查询。
这种复杂度的操作组合，非常适合使用分块数据结构来解决。分块的核心思想是“大段维护，小段朴素”，在查询和修改之间取得平衡。
我们将数组 分成大约
个块，每个块的大小也为
。
维护信息：
a[]: 原始数组。block[]: 一个辅助数组，其中block[i]存储了第个块内所有元素的有序拷贝。这个有序数组是快速查询前驱的关键。
lazy[]: 每个块的懒标记。lazy[b]记录了第个块需要统一增加的值。
操作实现：
-
区间增量
(l, r, x)- 对于完全包含在
[l, r]内的块：我们不需要修改块内的每一个元素，只需更新它们的懒标记即可：lazy[b] += x。这是的。
- 对于
l和r所在的、不完全包含的块（边界块）：我们需要进行朴素的单点修改。- 首先，下放（push down）该块的懒标记，即把
lazy[b]的值加到块内a[]数组的每一个元素上，然后清零lazy[b]。 - 接着，遍历
[l, r]在该块内的部分，对a[i]逐个加上 - 修改完成后，重新构建该块的有序拷贝
block[b]。这一步是必要的，以保证后续查询的正确性。
- 首先，下放（push down）该块的懒标记，即把
- 整个增量操作的复杂度为
，瓶颈在于边界块的重构。
- 对于完全包含在
-
区间前驱查询
(l, r, k)- 初始化一个结果
ans = -infinity(或一个极小值)。 - 对于完全包含在
[l, r]内的块：- 我们要在块
block[b][i] + lazy[b]。 - 因此，我们要在有序数组
block[b]中寻找小于k - lazy[b]的最大元素。这可以通过二分查找（例如upper_bound）高效完成。 - 用找到的元素更新
ans。
- 我们要在块
- 对于边界块：我们直接遍历
[l, r]在该块内的部分。对于每个元素a[i] + lazy[b]，如果它小于ans。 - 整个查询操作的复杂度为
- 初始化一个结果
由于 和
的范围，数组元素可能会很大，需要使用 64 位整型（
long long / long）来存储。
代码
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const long long INF = -2e18; // 使用一个足够小的数表示未找到
int n, m;
int block_size;
vector<long long> a;
vector<long long> lazy;
vector<vector<long long>> blocks;
vector<int> block_map;
// 重构指定块的有序版本
void rebuild(int b_idx) {
int start = b_idx * block_size;
int end = min((b_idx + 1) * block_size - 1, n - 1);
blocks[b_idx].clear();
for (int i = start; i <= end; ++i) {
blocks[b_idx].push_back(a[i]);
}
sort(blocks[b_idx].begin(), blocks[b_idx].end());
}
// 只将懒标记应用到原数组a，不重构
void apply_lazy(int b_idx) {
if (lazy[b_idx] == 0) return;
int start = b_idx * block_size;
int end = min((b_idx + 1) * block_size - 1, n - 1);
for (int i = start; i <= end; ++i) {
a[i] += lazy[b_idx];
}
lazy[b_idx] = 0;
}
void update(int l, int r, long long x) {
int start_block = block_map[l];
int end_block = block_map[r];
if (start_block == end_block) {
apply_lazy(start_block);
for (int i = l; i <= r; ++i) {
a[i] += x;
}
rebuild(start_block);
} else {
apply_lazy(start_block);
for (int i = l; i < (start_block + 1) * block_size; ++i) {
a[i] += x;
}
rebuild(start_block);
for (int i = start_block + 1; i < end_block; ++i) {
lazy[i] += x;
}
apply_lazy(end_block);
for (int i = end_block * block_size; i <= r; ++i) {
a[i] += x;
}
rebuild(end_block);
}
}
long long query(int l, int r, long long k) {
long long ans = INF;
int start_block = block_map[l];
int end_block = block_map[r];
if (start_block == end_block) {
for (int i = l; i <= r; ++i) {
if (a[i] + lazy[start_block] < k) {
ans = max(ans, a[i] + lazy[start_block]);
}
}
} else {
for (int i = l; i < (start_block + 1) * block_size; ++i) {
if (a[i] + lazy[start_block] < k) {
ans = max(ans, a[i] + lazy[start_block]);
}
}
for (int i = start_block + 1; i < end_block; ++i) {
long long target = k - lazy[i];
auto it = lower_bound(blocks[i].begin(), blocks[i].end(), target);
if (it != blocks[i].begin()) {
ans = max(ans, *(--it) + lazy[i]);
}
}
for (int i = end_block * block_size; i <= r; ++i) {
if (a[i] + lazy[end_block] < k) {
ans = max(ans, a[i] + lazy[end_block]);
}
}
}
return ans == INF ? -1 : ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
a.resize(n);
block_size = sqrt(n);
int num_blocks = (n + block_size - 1) / block_size;
lazy.assign(num_blocks, 0);
blocks.resize(num_blocks);
block_map.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
block_map[i] = i / block_size;
}
for (int i = 0; i < num_blocks; ++i) {
rebuild(i);
}
for (int i = 0; i < m; ++i) {
int type;
cin >> type;
if (type == 1) {
int l, r;
long long x;
cin >> l >> r >> x;
update(l - 1, r - 1, x);
} else {
int l, r;
long long k;
cin >> l >> r >> k;
cout << query(l - 1, r - 1, k) << "\n";
}
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int blockSize;
static long[] a;
static long[] lazy;
static ArrayList<Long>[] blocks;
static int[] blockMap;
static void rebuild(int bIdx) {
int start = bIdx * blockSize;
int end = Math.min((bIdx + 1) * blockSize - 1, n - 1);
blocks[bIdx].clear();
for (int i = start; i <= end; i++) {
blocks[bIdx].add(a[i]);
}
Collections.sort(blocks[bIdx]);
}
// 只将懒标记应用到原数组a，不重构
static void applyLazy(int bIdx) {
if (lazy[bIdx] == 0) return;
int start = bIdx * blockSize;
int end = Math.min((bIdx + 1) * blockSize - 1, n - 1);
for (int i = start; i <= end; i++) {
a[i] += lazy[bIdx];
}
lazy[bIdx] = 0;
}
static void update(int l, int r, long x) {
int startBlock = blockMap[l];
int endBlock = blockMap[r];
if (startBlock == endBlock) {
applyLazy(startBlock);
for (int i = l; i <= r; i++) {
a[i] += x;
}
rebuild(startBlock);
} else {
applyLazy(startBlock);
for (int i = l; i < (startBlock + 1) * blockSize; i++) {
a[i] += x;
}
rebuild(startBlock);
for (int i = startBlock + 1; i < endBlock; i++) {
lazy[i] += x;
}
applyLazy(endBlock);
for (int i = endBlock * blockSize; i <= r; i++) {
a[i] += x;
}
rebuild(endBlock);
}
}
static long query(int l, int r, long k) {
long ans = Long.MIN_VALUE;
int startBlock = blockMap[l];
int endBlock = blockMap[r];
if (startBlock == endBlock) {
for (int i = l; i <= r; i++) {
if (a[i] + lazy[startBlock] < k) {
ans = Math.max(ans, a[i] + lazy[startBlock]);
}
}
} else {
for (int i = l; i < (startBlock + 1) * blockSize; i++) {
if (a[i] + lazy[startBlock] < k) {
ans = Math.max(ans, a[i] + lazy[startBlock]);
}
}
for (int i = startBlock + 1; i < endBlock; i++) {
long target = k - lazy[i];
int idx = Collections.binarySearch(blocks[i], target);
if (idx < 0) {
idx = -idx - 1; // Insertion point
}
if (idx > 0) {
ans = Math.max(ans, blocks[i].get(idx - 1) + lazy[i]);
}
}
for (int i = endBlock * blockSize; i <= r; i++) {
if (a[i] + lazy[endBlock] < k) {
ans = Math.max(ans, a[i] + lazy[endBlock]);
}
}
}
return ans == Long.MIN_VALUE ? -1 : ans;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
a = new long[n];
blockSize = (int) Math.sqrt(n);
int numBlocks = (n + blockSize - 1) / blockSize;
lazy = new long[numBlocks];
blocks = new ArrayList[numBlocks];
blockMap = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
a[i] = Long.parseLong(st.nextToken());
blockMap[i] = i / blockSize;
}
for (int i = 0; i < numBlocks; i++) {
blocks[i] = new ArrayList<>();
rebuild(i);
}
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int type = Integer.parseInt(st.nextToken());
if (type == 1) {
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
long x = Long.parseLong(st.nextToken());
update(l - 1, r - 1, x);
} else {
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
long k = Long.parseLong(st.nextToken());
out.println(query(l - 1, r - 1, k));
}
}
out.flush();
}
}
import sys
import math
import bisect
def rebuild(b_idx):
start = b_idx * block_size
end = min((b_idx + 1) * block_size, n)
# Clear and rebuild
blocks[b_idx] = sorted(a[start:end])
# 只将懒标记应用到原数组a，不重构
def apply_lazy(b_idx):
if lazy[b_idx] == 0:
return
start = b_idx * block_size
end = min((b_idx + 1) * block_size, n)
for i in range(start, end):
a[i] += lazy[b_idx]
lazy[b_idx] = 0
def update(l, r, x):
start_block = l // block_size
end_block = r // block_size
if start_block == end_block:
apply_lazy(start_block)
for i in range(l, r + 1):
a[i] += x
rebuild(start_block)
else:
apply_lazy(start_block)
for i in range(l, (start_block + 1) * block_size):
a[i] += x
rebuild(start_block)
for i in range(start_block + 1, end_block):
lazy[i] += x
apply_lazy(end_block)
for i in range(end_block * block_size, r + 1):
a[i] += x
rebuild(end_block)
def query(l, r, k):
ans = -float('inf')
start_block = l // block_size
end_block = r // block_size
if start_block == end_block:
for i in range(l, r + 1):
val = a[i] + lazy[start_block]
if val < k:
ans = max(ans, val)
else:
for i in range(l, (start_block + 1) * block_size):
val = a[i] + lazy[start_block]
if val < k:
ans = max(ans, val)
for i in range(start_block + 1, end_block):
target = k - lazy[i]
# bisect_left finds insertion point, which is what we need
idx = bisect.bisect_left(blocks[i], target)
if idx > 0:
ans = max(ans, blocks[i][idx - 1] + lazy[i])
for i in range(end_block * block_size, r + 1):
val = a[i] + lazy[end_block]
if val < k:
ans = max(ans, val)
return int(ans) if ans != -float('inf') else -1
def solve():
global n, block_size, a, lazy, blocks
# Fast I/O
lines = sys.stdin.readlines()
n, m = map(int, lines[0].split())
a = list(map(int, lines[1].split()))
block_size = int(math.sqrt(n))
num_blocks = (n + block_size - 1) // block_size
lazy = [0] * num_blocks
blocks = [[] for _ in range(num_blocks)]
for i in range(num_blocks):
rebuild(i)
results = []
for line in lines[2:]:
parts = list(map(int, line.split()))
op = parts[0]
if op == 1:
l, r, x = parts[1], parts[2], parts[3]
update(l - 1, r - 1, x)
else:
l, r, k = parts[1], parts[2], parts[3]
results.append(str(query(l - 1, r - 1, k)))
print("\n".join(results))
solve()
算法及复杂度
- 算法：分块 (Block Decomposition)
- 时间复杂度：设块大小为
。修改操作涉及到两个边界块的重构和中间块的懒标记更新，复杂度为
。查询操作涉及到两个边界块的遍历和中间块的二分查找，复杂度为
。当
时，修改和查询的复杂度均为
。总时间复杂度为
。
- 空间复杂度：
，用于存储原数组、块的有序拷贝等。
京公网安备 11010502036488号