首页 > 其他分享 >*【学习笔记】(9) 分块

*【学习笔记】(9) 分块

时间：2023-05-24 22:11:33浏览次数：48  
标签：ch 分块 int 复杂度 sqrt 学习 完整 笔记

分块思想

引用一下 oi-wiki 的话：

分块的基本思想是：通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

数列/序列分块

引入

#6280. 数列分块入门 4

给定一长度为$ n$ 的数列，有 \(n\) 次操作。
操作分为两种：区间加，查询区间和。
\(1\le n\le5×10^4\)。

划分

首先将序列按每 \(T\) 个元素一块进行分块，并记录每块的区间和。
\(T\) 的大小需要根据实际要求选择，下文复杂度分析部分会详细解析。
划分过程的常用模板：

len = T; //根据实际要求选择一个合适的大小。
cnt = (n - 1) / len + 1; 
for(int i = 1; i <= cnt; ++ i) { //分配块左右边界。
  	L[i] = R[i - 1] + 1;
  	R[i] = min(n, L[i] + len - 1);
}
//分配元素所属的块编号。
for(int i = 1; i <= n; ++i) pos[i] = (i - 1) / len + 1;

查询

设查询区间 \([l,r]\) 的区间和。

  • 若 l,r 在同一块内，直接暴力求和即可。块长为 \(T\)，单次查询复杂度上界 \(O(T)\)。

  • 否则答案由三部分构成：

    1. 以 \(l\) 开头的不完整块的和。
    2. 以 \(r\) 结尾的不完整块的和。
    3. 中间的完整块的和。

对于 \(1、2\) 两部分，可暴力求和，复杂度上界 \(O(T)\)
。

对于 \(3\) ，直接查询预处理的完整块和即可，复杂度上界 \(O(nT)\)（查询所有的完整块）。

单次查询总复杂度上界 \(O(\dfrac{n}{T}+T)\)。

修改

修改操作的过程与查询操作相同，设修改区间为 \([l,r]\)。

  • 若 \(l,r\) 在同一块内，直接暴力修改，并更新区间和。块长为 \(T\)，单次修改复杂度上界 \(O(T)\)。

  • 否则将修改区间划分成三部分：

    1. 以 \(l\) 开头的不完整块。
    2. 以 \(r\) 结尾的不完整块。
    3. 中间的完整块。

\(1、2\) 直接暴力修改序列，\(3\) 给完整的块打上区间加的标记。
单次修改复杂度上界 \(O(\dfrac{n}{T}+T)\)。

复杂度分析

总复杂度为 \(O(n\times(nT+T))\)。
由均值不等式，\(\dfrac{n}{T}+T\le 2\sqrt{\dfrac{n}{T}\times T}\)，当且仅当 \(\dfrac{n}{T}=T\) 时等号成立，复杂度最低。
此时块大小为 \(\sqrt{n}\)，总复杂度 \(O(n\sqrt{n})\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], L[N], R[N], pos[N], del[N], sum[N];
void add(int l, int r, int c){
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) a[i] += c, sum[pos[i]] += c;
		return ;
	}
	for(int i = l; i <= R[pos[l]]; ++i) a[i] += c, sum[pos[i]] += c;
	for(int i = pos[l] + 1; i < pos[r]; ++i) del[i] += c;
	for(int i = L[pos[r]]; i <= r; ++i) a[i] += c, sum[pos[i]] += c;
}
int ask(int l, int r, int c){
	int res = 0;
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) (res += a[i] + del[pos[i]]) %= c;
		return res;
	}
	for(int i = l; i <= R[pos[l]]; ++i) (res += a[i] + del[pos[i]]) %= c;
	for(int i = pos[l] + 1; i < pos[r]; ++i) (res += sum[i] + del[i] * (R[i] - L[i] + 1)) %= c;
	for(int i = L[pos[r]]; i <= r; ++i) (res += a[i] + del[pos[i]]) %= c;
	return res;
}
signed main(){
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1, sum[pos[i]] += a[i];
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1);
	while(n--){
		int opt = read(), l = read(), r = read(), c = read();
		if(!opt) add(l, r, c);
		else printf("%lld\n", ask(l, r, c + 1));
	}
	return 0;
}

练习

#6277. 数列分块入门 1

区间加，单点查询

直接暴力分块
完整块 修改永久懒标记
两端不完整块暴力修改元素值
单点查询值 = 元素值 + 懒标记
完整块数量不超过 \(\sqrt{n}\)
, 两不完整块总长度不超过 \(2\sqrt{n}\)
总复杂度 \(O(n\sqrt{n})\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], L[N], R[N], pos[N], del[N];
void add(int l, int r, int c){
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) a[i] += c;
		return ;
	}
	for(int i = l; i <= R[pos[l]]; ++i) a[i] += c;
	for(int i = pos[l] + 1; i < pos[r]; ++i) del[i] += c;
	for(int i = L[pos[r]]; i <= r; ++i) a[i] += c;
}
int ask(int l){
	return a[l] + del[pos[l]];
}
signed main(){
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1);
	while(n--){
		int opt = read(), l = read(), r = read(), c = read();
		if(!opt) add(l, r, c);
		else printf("%lld\n", ask(r));
	}
	return 0;
}

#6278. 数列分块入门 2

区间加，区间查询小于给定值 元素数
同 \(1\), 先进行分块, 再分别考虑完整块与不完整块 :

  • 先不考虑 修改操作 :
    不完整块 可直接暴力查询
    对于完整块, 查询小于给定值元素数, 易联想到 lower_bound 操作
    由于分块后单个块较小, 则可直接暴力排序, 再通过 lower_bound 求得元素数
  • 再考虑 修改操作
    同样, 不完整块 可直接进行暴力修改
    对于完整块, 区间加后, 不影响它们之间的排名, 排序后 顺序不变
    进行区间加 \(x\) 后 再进行区间查询 \(y\) , 与 在区间加 \(x\) 之前, 区间查询 \(y - x\) , 得到的结果相同
    则可使用类似 \(1\) 的懒惰标记法 进行区间修改, 并根据懒标记调整查询的值

由上, 则需记录 未排序的数列 与 排序后的数列(需要进行 lower_bound)
可使用 vector 类, 来储存每一排序后的完整块

  • 修改时 :

    不完整块 暴力修改未排序数列, 将 原排序后的数列 重新赋值并排序 (为了便于 查询)
    其总长度不超过 \(2\sqrt{n}\), 单次排序复杂度 \(O(\sqrt{n}\log\sqrt{ n})\)
    完整块直接更新 懒标记即可, 其个数 不超过 \(\sqrt{n}\)
    则单次修改总复杂度为 \(O(\sqrt{n}+\sqrt{n}\log\sqrt{ n})\)

  • 查询时 :
    不完整块 暴力查询未排序数列, 其总长度不超过 \(2\sqrt{n}\)
    完整块 对排序后数列进行 lower_bound, 其个数 不超过 \(\sqrt{n}\), 单次 lower_bound 复杂度为 \(O(\sqrt{n}\log\sqrt{n})\)
    则单次修改总复杂度也为 \(O(\sqrt{n}+\sqrt{n}\log\sqrt{ n})\)

在预处理分块时 需要对整个数列进行排序预处理, 复杂度 \(O(n\log n)\)

则上述算法 总复杂度为 \(O(n\log n+\sqrt{n}\log\sqrt{ n})\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], L[N], R[N], pos[N], del[N];
vector<int> E[505];
void reset(int x){
	E[x].clear();
	for(int i = L[x]; i <= R[x]; ++i) E[x].push_back(a[i]);
	sort(E[x].begin(), E[x].end());
}
void change(int l, int r, int c){
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) a[i] += c;
		reset(pos[l]);
		return ;
	}
	for(int i = l; i <= R[pos[l]]; ++i) a[i] += c; reset(pos[l]);
	for(int i = pos[l] + 1; i < pos[r]; ++i) del[i] += c;
	for(int i = L[pos[r]]; i <= r; ++i) a[i] += c; reset(pos[r]);
}
int ask(int l, int r, int c){
	int res = 0;
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) res += (a[i] + del[pos[i]] < c);
		return res;
	}
	for(int i = l; i <= R[pos[l]]; ++i) res += (a[i] + del[pos[i]] < c);
	for(int i = pos[l] + 1; i < pos[r]; ++i) res += lower_bound(E[i].begin(), E[i].end(), c - del[i]) - E[i].begin();
	for(int i = L[pos[r]]; i <= r; ++i) res += (a[i] + del[pos[i]] < c);
	return res;
}
signed main(){
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
	for(int i = 1; i <= n; ++i) E[pos[i]].push_back(a[i]);
	for(int i = 1; i <= cnt; ++i) sort(E[i].begin(), E[i].end());
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1);
	while(n--){
		int opt = read(), l = read(), r = read(), c = read();
		if(!opt) change(l, r, c);
		else printf("%lld\n", ask(l, r, c * c));
	}
	return 0;
}

#6279. 数列分块入门 3

区间加，区间查询小于给定值 最大元素

  • 算法1 :
    套用 数列分块2 的做法, 在进行lower_bound时 求得每个块中 小于给定值 最大元素,
    再将多个块的答案合并 取最大值.
    总复杂度 \(O(n\log n + n\sqrt{n}\log\sqrt{n})\)

  • 算法2 :
    查询前驱 ? 来发 Splay
    可以对每个块 都维护一个 set , 来代替算法 1 中的排序数组.
    重赋值和插入操作 都会变得更方便 .

#include<bits/stdc++.h>
#define int long long
#define iter multiset<int>::iterator
using namespace std;
const int N = 1e5 + 5;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], L[N], R[N], pos[N], del[N];
multiset<int> E[1010];
void change(int l, int r, int c){
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) E[pos[l]].erase(a[i]), a[i] += c, E[pos[l]].insert(a[i]);
		return ;
	}
	for(int i = l; i <= R[pos[l]]; ++i) E[pos[l]].erase(a[i]), a[i] += c, E[pos[l]].insert(a[i]);
	for(int i = pos[l] + 1; i < pos[r]; ++i) del[i] += c;
	for(int i = L[pos[r]]; i <= r; ++i) E[pos[r]].erase(a[i]), a[i] += c, E[pos[r]].insert(a[i]);
}
int ask(int l, int r, int c){
	int res = -1;
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i)
			if(a[i] + del[pos[i]] < c) res = max(res, a[i] + del[pos[i]]);
		return res;
	}
	for(int i = l; i <= R[pos[l]]; ++i)
		if(a[i] + del[pos[i]] < c) res = max(res, a[i] + del[pos[i]]);
	for(int i = pos[l] + 1; i < pos[r]; ++i){
		iter it = E[i].lower_bound(c - del[i]);
		if(it == E[i].begin()) continue;
		res = max(res, *(--it) + del[i]);
	}
	for(int i = L[pos[r]]; i <= r; ++i)
		if(a[i] + del[pos[i]] < c) res = max(res, a[i] + del[pos[i]]);
	return res;
}
signed main(){
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
	for(int i = 1; i <= n; ++i) E[pos[i]].insert(a[i]);
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1);
	while(n--){
		int opt = read(), l = read(), r = read(), c = read();
		if(!opt) change(l, r, c);
		else printf("%lld\n", ask(l, r, c));
	}
	return 0;
}

#6280. 数列分块入门 4

区间加, 区间求和
上面有了。

#6281. 数列分块入门 5

区间开方，区间求和
对于求和操作 :
同 T4 , 维护完整块元素和.
不完整块暴力查询, 完整块查询 整块元素和.
显然, 单次求和复杂度为 \(O(\sqrt{n})\)

  • 对于修改操作 :
    不完整块 直接暴力开方 .
    对于完整块 :
    由于开方运算不满足 一系列运算律, 无法使用标记法.
    怎么办? 考虑直接暴力.
    众所周知,
    \(\lfloor{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{2^{31}}}}}}=1\rfloor}\) .
    对于一个数, 最多 5 次修改后 必然等于 1 或 0 .
    对于一个块, 最多 5 次修改后 必然全部由 1 或 0 组成 .
    而 \(\sqrt{1}=1\), \(\sqrt{0}=0\) , 修改操作对其不会有影响 .
    则可以标记一个完整块是否全为 1/0.
    若全为 1/0, 则无论其修改次数, 元素和都不会改变, 不进行修改操作.
    否则 直接暴力修改, 并在暴力修改时 完成对标记的更新.
    由于每个完整块的修改次数 \(≤5\) , 而不完整块的大小 \(≤\sqrt{n}\).
    则所有修改操作 总复杂度最大为 \(O(5n+\sqrt{n})\).
#include<bits/stdc++.h>
#define int long long
#define iter multiset<int>::iterator
using namespace std;
const int N = 1e5 + 5;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], L[N], R[N], pos[N], del[N], sum[N];
bool flag[N];
void solve(int x){
	if(flag[x]) return ;
	sum[x] = 0, flag[x] = 1;
	for(int i = L[x]; i <= R[x]; ++i){
		a[i] = sqrt(a[i]), sum[x] += a[i];
		if(a[i] > 1) flag[x] = 0;
	}
}
void change(int l, int r, int c){
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) sum[pos[i]] -= a[i], a[i] = sqrt(a[i]), sum[pos[i]] += a[i];
		return ;
	}
	for(int i = l; i <= R[pos[l]]; ++i) sum[pos[i]] -= a[i], a[i] = sqrt(a[i]), sum[pos[i]] += a[i];
	for(int i = pos[l] + 1; i < pos[r]; ++i) solve(i);
	for(int i = L[pos[r]]; i <= r; ++i) sum[pos[i]] -= a[i], a[i] = sqrt(a[i]), sum[pos[i]] += a[i];
}
int ask(int l, int r){
	int res = 0;
	if(pos[l] == pos[r]){
		for(int i = l; i <= r; ++i) res += a[i];
		return res;
	}
	for(int i = l; i <= R[pos[l]]; ++i) res += a[i];
	for(int i = pos[l] + 1; i < pos[r]; ++i) res += sum[i];
	for(int i = L[pos[r]]; i <= r; ++i) res += a[i];
	return res;
}
signed main(){
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1, sum[pos[i]] += a[i];
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1);
	while(n--){
		int opt = read(), l = read(), r = read(), c = read();
		if(!opt) change(l, r, c);
		else printf("%lld\n", ask(l, r));
	}
	return 0;
}

#6282. 数列分块入门 6

单点插入，单点查询

众所周知 , vector 的 insert 操作, 复杂度与 vector 内元素个数 呈正比.
则可使用分块 来构建多个vector , 以降低插入复杂度 :
插入时 枚举所有块, 将元素插入指定位置所在块中, 单次复杂度近似 \(O(\sqrt{n})\).
查询时 枚举所有块, 在指定位置所在块中查询 , 单次复杂度近似 \(O(\sqrt{n})\).
总复杂度近似 \(O(n\sqrt{n})\).

上述复杂度分析 都是基于 随机数据 的前提下的.
如果出题人恶意构造类似下方的数据 :

100000
1 1 1 1
1 1 1 1
1 1 1 1
...

上述做法会出现 不断插入同一块的情况 ,
单次插入会被卡到 \(O(n)\) , 总复杂度被卡到 \(O(n^2)\).

考虑 如何才能使各块的大小相对平均, 避免产生上述问题.
直接再分一遍块不就行了 !
为块的大小设定上限 , 在插入同时判断块的大小是否达到上限.
若达到上限, 枚举所有元素, 重新进行分块, 以平均块的大小.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], pos[N];
vector<int> E[N], tmp;
void rebuild(){
	tmp.clear();
	for(int i = 1; i <= cnt; ++i){
		int ll = E[i].size();
		for(int j = 0; j < ll; ++j) tmp.push_back(E[i][j]);
		E[i].clear();
	} 
	len = sqrt(tmp.size()), cnt = (tmp.size() - 1) / len + 1;
	for(int i = 0; i < tmp.size(); ++i) E[i / len + 1].push_back(tmp[i]);
	return ;
}
void insert(int x, int val){
	int pos1 = 1, pos2 = x;
	while(pos2 > E[pos1].size()) pos2 -= E[pos1].size(), ++pos1;
	E[pos1].insert(E[pos1].begin() + pos2 - 1, val);
	if(E[pos1].size() > 10 * len) rebuild();
	return ;
}
int ask(int x){
	int pos1 = 1, pos2 = x;
	while(pos2 > E[pos1].size()) pos2 -= E[pos1].size(), ++pos1;
	return E[pos1][pos2 - 1];
}
signed main(){
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
	for(int i = 1; i <= n; ++i) E[pos[i]].push_back(a[i]);
	while(n--){
		int opt = read(), l = read(), r = read(), c = read();
		if(!opt) insert(l, r);
		else printf("%lld\n", ask(r));
	}
	return 0;
}

#6283. 数列分块入门 7

区间加，区间乘，单点查询

如果只有区间乘操作, 只需要将 T1 的 + 改为 * 即可.
但是 区间加区间乘 同时存在, 需记录 两懒标记, 就需要注意懒标记与 数列值之间的关系
(以下, 使用 \(k\) 代表乘法懒标记, \(b\) 代表加法标记, \(x\) 代表数列值).

对于完整块的两修改操作 :

  • 当出现 先乘后加 时, 有 : \((kx+b)+y=kx+b+y\).
    若只修改 数列值 x , 则会出现: \([k(x+y)+b]=kx+ky+b≠kx+b+y\).

  • 当出现 先加后乘 时, 有 : \((kx+b)×y=kxy+by\).
    若只修改 数列值, 则会出现: $kxy+b≠kxy+by $.
    若只修改 乘法懒标记, 则会出现: \(kyx+b≠kxy+by\) .
    进行修改操作时 要进行多方面的考虑, 需要进行分类讨论
    吗, 当然是不需要的.
    不完整块较小 , 可以直接暴力处理 .
    先通过修改前的懒标记 求得整个块各元素值 , 并清空懒标记,
    再暴力修改数列值 , 即可避免上述情况发生.

对于完整块的两修改操作 :

  • 区间加时, 直接修改加法懒标记即可.
  • 区间乘时, 根据 乘法结合律有 :\((kx+b)×y=kxy+by\).
    则将 加法标记 与 乘法标记同乘即可.

单点查询, 即输出 \(kx+b\), 复杂度 \(O(1)\).

完整块数量不超过 \(\sqrt{n}\), 两不完整块总长度不超过 \(2\sqrt{n}\)
综上, 总复杂度为 \(O(n\sqrt{n})\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, mod = 1e4 + 7;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], L[N], R[N], pos[N], del1[N], del2[N];
void reset(int x){
	for(int i = L[x]; i <= R[x]; ++i) a[i] = (a[i] * del2[x] + del1[x]) % mod;
	del2[x] = 1, del1[x] = 0;
}
void add1(int l, int r, int c){
	if(pos[l] == pos[r]){
		reset(pos[l]); for(int i = l; i <= r; ++i) a[i] = (a[i] + c) % mod;
		return ;
	}
	reset(pos[l]); for(int i = l; i <= R[pos[l]]; ++i) a[i] = (a[i] + c) % mod;
	for(int i = pos[l] + 1; i < pos[r]; ++i) del1[i] = (del1[i] + c) % mod;
	reset(pos[r]); for(int i = L[pos[r]]; i <= r; ++i) a[i] = (a[i] + c) % mod;
}
void add2(int l, int r, int c){
	if(pos[l] == pos[r]){
		reset(pos[l]); for(int i = l; i <= r; ++i) a[i] = a[i] * c % mod;
		return ;
	}
	reset(pos[l]); for(int i = l; i <= R[pos[l]]; ++i) a[i] = a[i] * c % mod;
	for(int i = pos[l] + 1; i < pos[r]; ++i) del1[i] = del1[i] * c % mod, del2[i] = del2[i] * c % mod;
	reset(pos[r]); for(int i = L[pos[r]]; i <= r; ++i) a[i] = a[i] * c % mod;
}
int ask(int x){
	return (a[x] * del2[pos[x]] % mod + del1[pos[x]]) % mod;
}
signed main(){ 
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1), del2[i] = 1;
	while(n--){
		int opt = read(), l = read(), r = read(), c = read();
		if(!opt) add1(l, r, c);
		else if(opt == 1) add2(l, r, c);
		else if(opt == 2) printf("%lld\n", ask(r));
	}
	return 0;
}

#6283. 数列分块入门 8

区间赋值，查询区间等于给定值元素数

同T6 , 还是先想暴力.

对于修改操作, 不完整块 直接暴力修改 , 完整块打懒标记.
单次修改操作 , 复杂度显然为 \(O(\sqrt{n})\).

对于查询操作, 不完整块在暴力修改时 顺便暴力查询, 完整块分下列两种情况讨论 :

1. 有懒标记 , 则块内元素相同 , 直接判断标记与查询值 是否相同.
2. 无懒标记 , 没有什么好的处理方法 , 直接暴力查询.

若使一次查询, 其完整块查询操作 复杂度变为 \(O(n)\) , 需要使区间内完整块全部无懒标记.
而一次修改操作 , 只能使修改区间两端的 2 不完整块 懒标记清空,
若使一区间完整块懒标记全部清空, 需要先经过 \(\sqrt{n}\) 次修改操作
单次查询操作, 处理不完整块复杂度为 \(O(\sqrt{n})\) ,
而对于完整块的处理, 在无懒标记的情况下 可能会被卡到 \(O(n)\).
最多只会有 \(\sqrt{n}\) 次的修改操作
故上述算法 总复杂度 近似 \(O(n \sqrt{n})\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt;
int a[N], L[N], R[N], pos[N], same[N];
void reset(int x){
	if(same[x] == -1) return ;
	for(int i = L[x]; i <= R[x]; ++i) a[i] = same[x];
	same[x] = -1;
}
int solve(int l, int r, int c){
	int res = 0;
	if(pos[l] == pos[r]){
		reset(pos[l]); for(int i = l; i <= r; ++i) res += (a[i] == c), a[i] = c;
		return res;
	}
	reset(pos[l]); for(int i = l; i <= R[pos[l]]; ++i) res += (a[i] == c), a[i] = c;
	for(int i = pos[l] + 1; i < pos[r]; ++i){
		if(same[i] != -1) res += (R[i] - L[i] + 1) * (same[i] == c);
		else for(int j = L[i]; j <= R[i]; ++j) res += (a[j] == c);
		same[i] = c;
	}
	reset(pos[r]); for(int i = L[pos[r]]; i <= r; ++i) res += (a[i] == c), a[i] = c;
	return res;
}
signed main(){
	n = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1), same[i] = -1;
	while(n--){
		int l = read(), r = read(), c = read();
		printf("%lld\n", solve(l, r, c));
	}
	return 0;
}

#6283. 数列分块入门 9

查询区间最小众数

预处理出两个数组：

\(p[i][j]\)：表示第 \(i\) 个块 到第 \(j\) 个块的（最小的）众数。

\(s[i][j]\)：类似于前缀和，在前 \(i\) 个（包括 \(i\) ）个块中 \(j\) （离散化之后的值）出现了几次。

如何预处理 \(p,s\)

对于 \(s\) ，直接每个块扫一遍，复杂度 \(O(n \sqrt n)\)

对于 \(p\) ，双重循环枚举 \(i,j\)，开一个数组暴力统计每个数出现了多少次。复杂度 \(O(\sqrt n \sqrt n \sqrt n)=O(n \sqrt n)\)

如果 \(pos[r]-pos[l]\le2\) 直接暴力即可

如果 \(pos[r]-pos[l]>2\) ，

对于不完整块，直接暴力计算

对于完整块，就是之前预处理的 \(p[pos[l]+1][pos[r]-1]\)

众数数量就是 \(max(\)在不完整块内出现数字中的在\([l,r]\)中出现次数最大值，完整块内的出现次数最多的数字在\([l,r]\)中的出现次数\()\)，取最小的那个数就好了，由于这道题之前就打过了，码风有点不大一样，应该也是看得懂的。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
void read(int &o){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	o=x*f;
}
int n,m,len,cnt;
int a[N],b[N];
int l[N],r[N];
int sum[N];
int id[405][405],p[405][405],s[405][N]; //p[i][j] 表示块i 到 块j 的最小众数个数   s[i][j] 前i块 j 出现次数 
int Get(int x){
	int k=x/len;
	k+=(x%len?1:0);
	return k;
}
int main(){
	read(n);
	len=sqrt(n);
	cnt=(n-1)/len+1;
	for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
	sort(b+1,b+1+n);
	int tot=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=cnt;i++) l[i]=r[i-1]+1,r[i]=(i==cnt?n:l[i]+len-1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
	for(int i=1;i<=cnt;i++){
		int B[N]={0},ID=0,P=0;
		for(int j=i;j<=cnt;j++){
			for(int k=l[j];k<=r[j];k++){
				B[a[k]]++;
				if(B[a[k]]>P){
					P=B[a[k]];
					ID=a[k]; 
				}else if(B[a[k]]==P) ID=min(a[k],ID);
			}
			id[i][j]=ID,p[i][j]=P;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=n;j++) s[i][a[j]]=s[i-1][a[j]];
		for(int j=l[i];j<=r[i];j++) s[i][a[j]]++;
	}
	int x=0;
	while(n--){ 
		int ll,rr,ans=0;
		read(ll),read(rr);
		memset(sum,0,sizeof(sum));
		int ql=Get(ll),qr=Get(rr);
		if(qr-ql<=2){
			for(int i=ll;i<=rr;i++){
				sum[a[i]]++;
				if(sum[ans]<sum[a[i]]) ans=a[i];
				else if(sum[a[i]]==sum[ans]) ans=min(ans,a[i]);
			} 
			printf("%d\n",x=b[ans]); 
		}else{
			ans=id[ql+1][qr-1];
			for(int i=ll;i<=r[ql];i++) sum[a[i]]++;
			for(int i=l[qr];i<=rr;i++) sum[a[i]]++;
			int maxnum=0,maxn=0;
			for(int i=ll;i<=r[ql];i++){
				int val=s[qr-1][a[i]]-s[ql][a[i]]+sum[a[i]];
				if(val>maxn){
					maxn=val;
					maxnum=a[i];
				}else if(val==maxn) maxnum=min(maxnum,a[i]);
			}
			for(int i=l[qr];i<=rr;i++){
				int val=s[qr-1][a[i]]-s[ql][a[i]]+sum[a[i]];
				if(val>maxn){
					maxn=val;
					maxnum=a[i];
				}else if(maxn==val) maxnum=min(maxnum,a[i]);
			}
			int ss=sum[ans]+p[ql+1][qr-1];
			if(maxn>ss) ans=maxnum;
			else if(maxn==ss) ans=min(ans,maxnum);
			printf("%d\n",x=b[ans]);
		}
	}
	return 0;
}

P4135 作诗

询问区间出现次数为正偶数的数的个数。

其实与区间众数那道题类似，实现预处理出块与块之间的答案，再根据散块内的值分类讨论进行修改。

记得位运算时要加括号来保证优先级，调了好久。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 51;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, len, cnt, q, ans, c, top;
int a[N], L[N], R[N], pos[N], num[351][N], f[351][351];
//num[i][j] 表示第 i 块到 n 中，j 的出现次数 f[i][j] 表示第 i 块到第 j 块的答案 
int stk[N], cc[N];
signed main(){
	n = read(), c = read(), q = read(); len = sqrt(n), cnt = (n - 1) / len + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
	for(int i = 1; i <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1);
	for(int i = 1; i <= cnt; ++i){
		int t = 0;
		for(int j = L[i]; j <= n; ++j){
			++num[i][a[j]];
			if(num[i][a[j]] > 1 && (num[i][a[j]] & 1)) --t;
			else if((num[i][a[j]] & 1) == 0) ++t;
			f[i][pos[j]] = t;
		}
	}
	while(q--){
		int l = (read() + ans) % n + 1, r = (read() + ans) % n + 1;
		if(l > r) swap(l, r); ans = 0;
		if(pos[l] == pos[r]){
			for(int i = l; i <= r; ++i) ++cc[a[i]], stk[++top] = a[i];
			while(top){
				if(cc[stk[top]]) ans += (cc[stk[top]] & 1) ^ 1;
				cc[stk[top--]] = 0;
			}
			printf("%d\n", ans); continue;
		}
		if(pos[l] + 1 <= pos[r] - 1) ans = f[pos[l] + 1][pos[r] - 1];
		for(int i = l; i <= R[pos[l]]; ++i) ++cc[a[i]], stk[++top] = a[i];
		for(int i = L[pos[r]]; i <= r; ++i) ++cc[a[i]], stk[++top] = a[i];
		while(top){
			int t = stk[top];
			if(cc[t] != 0){
				if(num[pos[l] + 1][t] - num[pos[r]][t] > 0 && ((num[pos[l] + 1][t] - num[pos[r]][t]) & 1) == 0 && (cc[t] & 1)) ans--;
				else if(num[pos[l] + 1][t] - num[pos[r]][t] > 0 && ((num[pos[l] + 1][t] - num[pos[r]][t]) & 1) && (cc[t] & 1)) ans++;
				else if(num[pos[l] + 1][t] - num[pos[r]][t] == 0 && ((cc[t] & 1) == 0)) ans++;
			}
			cc[stk[top--]] = 0;
		}
		printf("%d\n", ans);
	}
	return 0;
}

值域分块

顾名思义，就是将值域分块，统计 值域为\([l,r]\)的答案，一般与莫队一起使用。

P4396 [AHOI2013]作业

求区间 \([l,r]\) 值在值域 \([a,b]\) 的数的个数和数的种类。

区间询问显然可以用莫队来实现，对于值域 \([a,b]\) 的查询可以用值域分块来实现。（不知道为什么好像分块的时候根据序列分块要比根据值域分块要快）

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 51;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, m, len, cnt;
int a[N], pos[N], L[N], R[N], ans[N], res[N];
// ans[i] 是不同数的种类
// res[i] 是数的数量
int sumr[N], sum[N], suma[N];
// sum[i] 表示 i 这个值的数量
// sumr[i] 表示 pos[i] 这个块的 res
// suma[i] 表示 pos[i] 这个块的 ans
struct Query {
    int id, l, r, a, b;
    bool operator<(const Query &A) const { return pos[l] ^ pos[A.l] ? pos[l] < pos[A.l] : r < A.r; }
} q[N];
inline void add(int x) {
    ++sum[a[x]], ++sumr[pos[a[x]]];
    if (sum[a[x]] <= 1)
        ++suma[pos[a[x]]];
}
inline void del(int x) {
    --sum[a[x]], --sumr[pos[a[x]]];
    if (sum[a[x]] <= 0)
        --suma[pos[a[x]]];
}
inline int get_ans(int l, int r) {
    int ss = 0;
    if (l > r)
        return 0;
    if (pos[l] == pos[r]) {
        for (int i = l; i <= r; ++i) ss += (sum[i] >= 1);
        return ss;
    }
    for (int i = l; i <= R[pos[l]]; ++i) ss += (sum[i] >= 1);
    for (int i = pos[l] + 1; i <= pos[r] - 1; ++i) ss += suma[i];
    for (int i = L[pos[r]]; i <= r; ++i) ss += (sum[i] >= 1);
    return ss;
}
inline int get_res(int l, int r) {
    int ss = 0;
    if (l > r)
        return 0;
    if (pos[l] == pos[r]) {
        for (int i = l; i <= r; ++i) ss += sum[i];
        return ss;
    }
    for (int i = l; i <= R[pos[l]]; ++i) ss += sum[i];
    for (int i = pos[l] + 1; i <= pos[r] - 1; ++i) ss += sumr[i];
    for (int i = L[pos[r]]; i <= r; ++i) ss += sum[i];
    return ss;
}
int main() {
    n = read(), m = read();
    len = sqrt(n);
    for (int i = 1; i <= n; ++i) a[i] = read(), pos[i] = (i - 1) / len + 1;
    for (int i = 1; i <= m; ++i) q[i] = (Query){ i, read(), read(), read(), read() };
    sort(q + 1, q + 1 + m);
    for (int i = 1; i <= n; ++i) L[i] = R[i - 1] + 1, R[i] = min(n, L[i] + len - 1);
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        while (r < q[i].r) add(++r);
        while (l > q[i].l) add(--l);
        while (l < q[i].l) del(l++);
        while (r > q[i].r) del(r--);
        res[q[i].id] = get_res(q[i].a, q[i].b);
        ans[q[i].id] = get_ans(q[i].a, q[i].b);
    }
    for (int i = 1; i <= m; ++i) printf("%d %d\n", res[i], ans[i]);
    return 0;
}

参考资料： 「笔记」分块

标签：ch,分块,int,复杂度,sqrt,学习,完整,笔记
From： https://www.cnblogs.com/jiangchen4122/p/17417627.html

相关文章

  • 【学习笔记】(15) Kruskal 重构树
    前置知识：kruskal求最小生成树，倍增。1.算法简介以下所有讨论基于最小生成树。在Kruskal求最小生成树的过程：将所有边按照边权排序，若当前边\((u,v)\)两端不连通，则往生成树边集\(E\)中加入\((u,v)\)并连接\(u,v\)。使用并查集维护连通性。如果能用某种结构描述每条边......
  • GitlabCI学习笔记之三：GitLabRunner pipeline语法之tags allow_faillure when retry ti
    1.tags用于从允许运行该项目的所有Runner列表中选择特定的Runner,在Runner注册期间，您可以指定Runner的标签。tags可让您使用指定了标签的runner来运行作业,此runner具有ruby和postgres标签。示例给定带有osx标签的OSXRunner和带有windows标签的WindowsRunner，以下作业将在......
  • java基于springboot+vue的书籍学习平台管理系统，学期学习论坛管理系统，附源码+数据库+lw
    1、项目介绍困扰管理层的许多问题当中,书籍学习将会是不敢忽视的一块。但是管理好书籍学习又面临很多麻烦需要解决,在工作琐碎,记录繁多的情况下将书籍学习的当前情况反应给相关部门决策,等等。在此情况下开发一款书籍学习平台，于是乎变得非常合乎时宜。经过网上调查和搜集数据,......
  • redis学习4集群--黑马
    主从复制将master中的数据有效的复制到slave中master写数据执行写操作时，将出现变化的数据自动同步到slave读数据（可忽略）slave读数据写数据（禁止）主从连接(slave连接master)方式一：客户端发送命令slaveof方式二：启动服务器参数redis-server-slaveof方式三：服务器配......
  • C语言学习记录04
    逻辑操作符：条件操作符||三目操作符：例：//i＞j成立，为真，所以i为真，j为假，所以结果为i。逗号表达式：下表引用操作符：函数调用操作符：常见关键字：命名规则：......
  • MySQL学习基础篇Day9
    6.事务6.1事务简介事务是一组操作的集合，它是一个不可分割的工作单位，事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求，即这些操作要么同时成功，要么同时失败。就比如:张三给李四转账1000块钱，张三银行账户的钱减少1000，而李四银行账户的钱要增加1000。这一组操......
  • 五月读书笔记二《人件集》
    继续阅读《人件集》后，体会到软件开发团队如果想要在项目中获得最大限度的成功，取决于团队中的成员能否形成技术性一致意见。但为什么这点如此重要呢？是不是团队成员只要在诸如目录表格的布局上达成一致，或者建立一个很好的错误汇报机制就行了呢？技术性一致意见指的并不是与同事打成......
  • 我的软考复习笔记【中级软件设计师】
    目录内聚与耦合内聚耦合统一过程(UP)软件体系结构风格软件能力成熟度模型（CMM）集成测试策略软件测试方法黑盒测试白盒测试需求UML分类协作图的边界类控制类实体类怎么区别null用例图的关系泛化(Inheritance)扩展（extend）：包含（include）：快速辨认类图的符号1.关联2.泛化3.聚合组件图设......
  • LaTeX 的学习笔记
    摘自我的洛谷博客该文章被打开的次数（包括洛谷平台）：\(\LaTeX\)中所有命令都以\开头，后面可以跟一个花括号，代表参数。\documentclass{}指定了文章类型，有article（普通文章）、book（书）、beamer（幻灯片），如果要显示中文，有ctexart（普通文章），ctexbook（书），同时要指定文档的编码类型：\document......
  • SQL高级语法学习总结（二）
    SQL高级语法学习总结（一）。现在我们接着说sql的高级用法。SQLCREATEDATABASE语法CREATEDATABASEdbname;CREATEDATABASE语句用于创建数据库。 SQLCREATETABLE语法CREATETABLEtable_name(column_name1data_type(size),column_name2data_type(size),column_name3dat......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99