数列分块解决区间更新+区间最值问题(Solving the interval update + interval maximum problem by sequence blocks)

题目大意:

给定一个大小为 \(n\) 的数列 \(a_1, a_2, \ldots, a_n\),你需要对这个数列进行 \(m\) 次操作,操作包含如下两种类型:

  • 1 x y z :将区间 \([x,y]\) 范围内的所有元素更新为 \(z\)(即:\(a_x, a_{x+1}, \ldots, a_y\) 的值都将变为 \(z\));
  • 2 x y :查询区间 \([x,y]\) 范围内所有元素的最大值。

对于 \(100\%\) 的数据,\(1 \le n,m \le 2 \times 10^5, op \in [1,2],1 \le x \le y \le n, 1 \le z,a_i \le 10^9\)

解题思路:

  • tag[i] 维护分块 \(i\) 在整体更新的情况下的数值;
  • sum[i] 维护分块 \(i\) 在任意时刻的最大值。

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
int n, blo, m, a[maxn], bl[maxn], tag[505], mx[505], op, x, y, z;	
// blo=sqrt(n)表示每一个分块的大小  block分块 
// bl[i] 表示第i个点所属的分块编号 
// 区间更新[l,r]全部更新为z
// tag[x]表示第x个分块在全部一样(整体更新)的情况下的数值
// mx[x]表示第x个分块的最大值 

// 将tag[x]的值全部更新到属于第x个分块的所有元素 
void recover(int x) {
	// [(x-1)*blo+1, min(x*blo, n)]
	if (tag[x]) {
		for (int i = (x-1)*blo+1; i <= min(x*blo, n); i ++)
			a[i] = tag[x];
		mx[x] = tag[x]; // 何时何地mx[x]维护的都是区间的最大值 
		tag[x] = 0;
	}
}

// (重新)计算mx[x]的值 
void calmx(int x) {
	mx[x] = 0;
	for (int i = (x-1)*blo+1; i <= min(x*blo, n); i ++)
		mx[x] = max(mx[x], a[i]);
}

void update(int l, int r, int z)
{
	// 1. 处理a[l]所在的分块(单独处理) 
	recover(bl[l]);
	for (int i = l; i <= min(bl[l]*blo, r); i ++)
		a[i] = z;
	calmx(bl[l]);
	// 2. 处理a[r]所在的分块(单独处理) 
	if (bl[l] != bl[r]) {
		recover(bl[r]);
		for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
			a[i] = z;
		calmx(bl[r]);
	}
	// 3. 处理 bl[l]+1 到 bl[r]-1 这些中间的完整的分块
	for (int i = bl[l]+1; i < bl[r]; i ++)
		mx[i] = tag[i] = z;
} 

// 查询区间[l,r]的最大值 
int query(int l, int r)
{
	int res = 0;
	// 1. 处理a[l]所在的分块(单独处理) 
	recover(bl[l]);
	for (int i = l; i <= min(bl[l]*blo, r); i ++)
		res = max(res, a[i]);
	// 2. 处理a[r]所在的分块(单独处理) 
	if (bl[l] != bl[r]) {
		recover(bl[r]);
		for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
			res = max(res, a[i]);
	}
	// 3. 处理 bl[l]+1 到 bl[r]-1 这些中间的完整的分块
	for (int i = bl[l]+1; i < bl[r]; i ++)
		res = max(res, mx[i]);
	return res;
} 

int main()
{
	scanf("%d%d", &n, &m);
	blo = sqrt(n);
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d", a+i);
		bl[i] = (i - 1) / blo + 1;
		mx[bl[i]] = max(mx[bl[i]], a[i]);
	}
	while (m --) {
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {	// 区间[x,y]全部更新为z 
			scanf("%d", &z);
			update(x, y, z);
		}
		else {	// 查询区间[x,y]的最大值 
			printf("%d\n", query(x, y));
		}
	}
	return 0;
}
————————

Main idea of the title:

Given a sequence of numbers \ (a_1, a_2, \ ldots, a_n \) of size \ (n \), you need to perform \ (m \) operations on this sequence. The operations include the following two types:

  • 1 X Y Z: update all elements within the range of \ ([x, y] \) to \ (Z \) (that is, the values of \ (a_x, a_{x + 1}, \ ldots, a_y \) will become \ (Z \));
  • 2 x y: the maximum value of all elements within the query interval \ ([x, y] \).

For data of \ (100 \% \), \ (1 \ Le n, m \ le 2 \ times 10 ^ 5, Op \ in [1,2], 1 \ Le x \ Le y \ Le n, 1 \ Le Z, a_i \ Le 10 ^ 9 \)

Problem solving ideas:

  • Tag [i] maintain the value of block \ (I \) in the case of overall update;
  • Sum [i] maintain the maximum value of block \ (I \) at any time.

Sample program:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
int n, blo, m, a[maxn], bl[maxn], tag[505], mx[505], op, x, y, z;	
// blo=sqrt(n)表示每一个分块的大小  block分块 
// bl[i] 表示第i个点所属的分块编号 
// 区间更新[l,r]全部更新为z
// tag[x]表示第x个分块在全部一样(整体更新)的情况下的数值
// mx[x]表示第x个分块的最大值 

// 将tag[x]的值全部更新到属于第x个分块的所有元素 
void recover(int x) {
	// [(x-1)*blo+1, min(x*blo, n)]
	if (tag[x]) {
		for (int i = (x-1)*blo+1; i <= min(x*blo, n); i ++)
			a[i] = tag[x];
		mx[x] = tag[x]; // 何时何地mx[x]维护的都是区间的最大值 
		tag[x] = 0;
	}
}

// (重新)计算mx[x]的值 
void calmx(int x) {
	mx[x] = 0;
	for (int i = (x-1)*blo+1; i <= min(x*blo, n); i ++)
		mx[x] = max(mx[x], a[i]);
}

void update(int l, int r, int z)
{
	// 1. 处理a[l]所在的分块(单独处理) 
	recover(bl[l]);
	for (int i = l; i <= min(bl[l]*blo, r); i ++)
		a[i] = z;
	calmx(bl[l]);
	// 2. 处理a[r]所在的分块(单独处理) 
	if (bl[l] != bl[r]) {
		recover(bl[r]);
		for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
			a[i] = z;
		calmx(bl[r]);
	}
	// 3. 处理 bl[l]+1 到 bl[r]-1 这些中间的完整的分块
	for (int i = bl[l]+1; i < bl[r]; i ++)
		mx[i] = tag[i] = z;
} 

// 查询区间[l,r]的最大值 
int query(int l, int r)
{
	int res = 0;
	// 1. 处理a[l]所在的分块(单独处理) 
	recover(bl[l]);
	for (int i = l; i <= min(bl[l]*blo, r); i ++)
		res = max(res, a[i]);
	// 2. 处理a[r]所在的分块(单独处理) 
	if (bl[l] != bl[r]) {
		recover(bl[r]);
		for (int i = (bl[r]-1)*blo+1; i <= r; i ++)
			res = max(res, a[i]);
	}
	// 3. 处理 bl[l]+1 到 bl[r]-1 这些中间的完整的分块
	for (int i = bl[l]+1; i < bl[r]; i ++)
		res = max(res, mx[i]);
	return res;
} 

int main()
{
	scanf("%d%d", &n, &m);
	blo = sqrt(n);
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d", a+i);
		bl[i] = (i - 1) / blo + 1;
		mx[bl[i]] = max(mx[bl[i]], a[i]);
	}
	while (m --) {
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {	// 区间[x,y]全部更新为z 
			scanf("%d", &z);
			update(x, y, z);
		}
		else {	// 查询区间[x,y]的最大值 
			printf("%d\n", query(x, y));
		}
	}
	return 0;
}