分块¶
分块要注意块长与块数。在仅有其中一个决定时间复杂度时，要在空间和时间上取舍。两个共同决定时，要注意平衡。
分块可以实现的功能步线段树更多。但是n不能超过1e5（1000ms）。
分块¶
分块是一种用于处理数组问题的技巧，它将数组分成若干块，并在每个块上执行操作以优化时间复杂度。分块技术通常用于处理数组上的区间查询和更新问题，它可以在某些情况下提供比树状数组或线段树更简单的实现，尽管其时间复杂度可能不如这些数据结构。
以下是分块技术的基本原理和实现方式：
基本概念¶
-
块大小：将数组分成大小相等的块，通常块大小是sqrt(n)（n是数组的长度）。
-
块内操作：对于块内的操作，可以直接遍历块内的元素进行处理。
-
跨块操作：对于跨越多个块的操作，可以分别处理每个块，然后合并结果。
分块的构建¶
分块通常不需要显式的构建过程，但需要定义块的大小，并根据块大小来组织数据。
int n; // 数组长度
int block_size = sqrt(n); // 块大小
vector<int> arr(n); // 原始数组
分块操作¶
单点更新¶
单点更新操作可以直接在原数组上进行。
void change(int x,int a){
bv[x/B]+=a-v[x];
v[x]=a;
}
区间查询¶
区间查询操作需要处理两种情况：跨块的查询和块内的查询。
int query(int x,int y){
int res=0;
if(x/B==y/B){
for(itn i=x;i<=y;i++){
res+=v[i];
}
return res;
}
for(int i=x;i/B==x/B&&i<n;i++){
res+=v[i];
}
for(int i=y;i/B==y/B&&i>=0;i--){
res+=v[i];
}
for(itn i=x/B+1;i!=y/B;i++){
res+=bv[i];
}
return res;
}
区间更新¶
区间更新操作通常需要对每个块进行处理。和区间查询类似。
分块的优势和局限¶
优势¶
-
实现简单，不需要复杂的树形结构。
-
在某些问题中，分块可以提供较优的时间复杂度，尤其是当操作次数较少时。
局限¶
-
时间复杂度通常不如树状数组或线段树，尤其是在大量查询和更新操作时。
-
对于区间更新问题，分块通常需要O(n)的时间复杂度，而线段树可以提供O(log n)的更新时间复杂度。
总结¶
分块技术是一种处理数组问题的有效方法，它通过将数组分成块来简化区间操作。尽管它不是万能的解决方案，但在某些情况下，分块可以提供简单且有效的解决方案。分块技术适用于那些不经常更新或查询的数组问题，或者当问题规模不是非常大时。
例题 #1 [TJOI2009] 开关¶
现有 \(n\) 盏灯排成一排，从左到右依次编号为：\(1\)，\(2\)，……，\(n\)。然后依次执行 \(m\) 项操作。
操作分为两种：
-
指定一个区间 \([a,b]\)，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
-
指定一个区间 \([a,b]\)，要求你输出这个区间内有多少盏灯是打开的。
灯在初始时都是关着的。
输入格式
第一行有两个整数 \(n\) 和 \(m\)，分别表示灯的数目和操作的数目。
接下来有 \(m\) 行，每行有三个整数，依次为：\(c\)、\(a\)、\(b\)。其中 \(c\) 表示操作的种类。
-
当 \(c\) 的值为 \(0\) 时，表示是第一种操作。
-
当 \(c\) 的值为 \(1\) 时，表示是第二种操作。
\(a\) 和 \(b\) 则分别表示了操作区间的左右边界。
对于全部的测试点，保证 \(2\le n\le 10^5\)，\(1\le m\le 10^5\)，\(1\le a,b\le n\)，\(c\in\{0,1\}\)。
我们发现，这道题可以使用线段树完成！但是我们也发现，我们不想写线段树！因为它太长了！于是我们选线段树的替代品——分块！
分块！
我们把一段序列\(1\sim n\) 分成$ \lfloor\sqrt{n}\rfloor$份，可以真快修改的就一起修改，负责直接朴素修改。这样子在时间复杂度上会有所让步，但是它的代码简洁易懂，扩展性强。
//j0, j1 , jn , y1 , y0 , yn不能用：这是个函数（非常的高级）
#include <bits/stdc++.h>
const int N=1e5+5;
int op[N],kuai[N],n,m,sn;
using namespace std;
void change(int a,int b){
int p=b-b%sn;
while((a)%sn){
op[a]=1-op[a];
if(op[a])kuai[a/sn]++;
else kuai[a/sn]--;
a++;
}
while(a<p){
kuai[a/sn]=sn-kuai[a/sn];
a+=sn;
}
while(a<=b){
op[a]=1-op[a];
if(op[a])kuai[a/sn]++;
else kuai[a/sn]--;
a++;
}
}
void query(int a,int b){
int ans=0;
int p=b-b%sn;
while((a)%sn){
if(op[a])ans++;a++;
}
while(a<p){
ans+=kuai[a/sn];
a+=sn;
}
while(a<=b){
if(op[a])ans++;
a++;
}
cout<<ans<<endl;
}
int main(){
//ios::sync_which_stdio(false);
cin>>n>>m;
sn=sqrt(n);
for(int i=1;i<=m;i++){
int a,b,c;
cin>>c>>a>>b;
if(c==0){
change(a,b);
}else{
query(a,b);
}
}
return 0;
}
/*
Edit by Ntsc.
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define rd read()
#define ot write
#define nl putchar('\n')
inline int rd{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out){
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N=4e5+5;
const int M=5e4+5;
const int INF=2e18+5;
const int MOD=1e9+7;
const int BASE=17737;
bool f1;
int m;
int n,tr[N],tag[N];
bool f2;
void pushup(int x){
tr[x]=tr[x<<1]+tr[x<<1|1];
}
void addtag(int x,int l,int r){
tr[x]=r-l+1-tr[x];
tag[x]^=1;
}
void pushdown(int x,int l,int r){
int mid=l+r>>1;
if(!tag[x])return ;
addtag(x<<1,l,mid);
addtag(x<<1|1,mid+1,r);
tag[x]=0;
}
void change(int x,int l,int r,int pl,int pr){
if(l>=pl&&r<=pr){
addtag(x,l,r);
// cerr<<"ck";
return ;
}
pushdown(x,l,r);
int mid=l+r>>1;
if(pl<=mid)change(x<<1,l,mid,pl,pr);
if(pr>mid)change(x<<1|1,mid+1,r,pl,pr);
pushup(x);
}
int query(int x,int l,int r,int pl,int pr,int tg){
if(l>=pl&&r<=pr){
return tr[x];
}
pushdown(x,l,r);
int res=0;
int mid=l+r>>1;
if(pl<=mid)res+=query(x<<1,l,mid,pl,pr,tg^tag[x]);
if(pr>mid)res+=query(x<<1|1,mid+1,r,pl,pr,tg^tag[x]);
return res;
}
signed main(){
n=rd,m=rd;
for(int i=1;i<=m;i++){
int op=rd;
int a=rd,b=rd;
if(op){
cout<<query(1,1,n,a,b,0)<<endl;
}else{
change(1,1,n,a,b);
}
}
return 0;
}
/*
*/
例题 #2¶
题目描述¶
这次的任务是：在伴随着数字改变的情况下，试试统计某段的和。
输入格式
第一行两个整数n和m，表示有一个长度为n个序列和m个操作
接下来m行，每行的内容属于以下一种：
Change x a：把第x个数改成a
Query x y：求出[x,y]这段区间的和。
使用分块实现
分块无论修改，还是查询，对于一些题目的答案可能存在的地方，都是由以下几个部分组成的：
-
左边残缺块（暴力枚举）
-
中间整块
-
右边残缺块（暴力枚举）
然后把这些部分的答案merge即可。
代码¶
const int N = 5e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int n;
int B;
namespace BD{
int v[N];
int bv[N];
void change(int x,int a){
bv[x/B]+=a-v[x];
v[x]=a;
}
int query(int x,int y){
int res=0;
if(x/B==y/B){
for(itn i=x;i<=y;i++){
res+=v[i];
}
return res;
}
for(int i=x;i/B==x/B&&i<n;i++){
res+=v[i];
}
for(int i=y;i/B==y/B&&i>=0;i--){
res+=v[i];
}
for(itn i=x/B+1;i!=y/B;i++){
res+=bv[i];
}
return res;
}
void build(){
for(int i=0;i<n;i++){
bv[i/B]+=v[i];
}
}
}using namespace BD;
void solve(){
n=rd;
int m=rd;
B=sqrt(n)+1;
for(itn i=0;i<n;i++){
v[i]=rd;
}
build();
while(m--){
string s;
cin>>s;
int a=rd,b=rd;
if(s[0]=='Q'){
cout<<query(a-1,b-1)<<endl;
}else{
change(a-1,b);
}
}
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
例题 #3 刷漆升级¶
内存限制：128 MiB 时间限制：2000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
题目描述
这次的刷漆问题升级啦。 有编号为0到n-1的n面墙，操作是每次把连续编号的一段墙刷成c颜色，询问是问某段有多少面墙的颜色是c。
输入格式
第一行两个整数n和m
第二行n个整数，表示每面墙初始的颜色。
接下里m行，每行属于下列一种：
1 a b c：把编号[a,b]的墙刷成c颜色
2 a b c: 询问编号[a,b]有多少面墙的颜色是c。
输出格式
对于每个询问输出相应的结果。
对于30%的数据，n和m的范围[1,1000];
对于100%的数据，n和m的范围[1,100000];
需要块tag。要处理好tag和原数据的关系：
-
有tag时看tag
-
一旦块内数据存在（或者将要存在）和tag不符时，下放并且删除tag。
// Problem: C. 刷漆升级
// Contest: LibreOJ - S
// URL: http://www.nfls.com.cn:20035/contest/2100/problem/3
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
// #define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
// const int INF=1e18+7;
/*
策略
*/
struct Node{
int op;
int a,b,c;
}q[N];
int v[N];
int n;
namespace BD{
int B;
int vb[350][100002];
int tag[350];
inline int getId(int i){
return i/B;
}
void change(itn a,int b,int c){
// cdbg("cg",a,b,c);
int id=getId(a);
for(int i=id*B;i<=id*B+B-1;i++){
if(i>=a&&i<=b)vb[id][v[i]]--,v[i]=c,vb[id][c]++;
else if(tag[id]) vb[id][v[i]]--,v[i]=tag[id],vb[id][tag[id]]++;
}
tag[id]=0;
for(int i=id+1;i<getId(b);i++){
tag[i]=c;
}
id=getId(b);
if(id!=getId(a)){
for(int i=id*B;i<=id*B+B-1;i++){
if(i>=a&&i<=b)vb[id][v[i]]--,v[i]=c,vb[id][c]++;
else if(tag[id]) vb[id][v[i]]--,v[i]=tag[id],vb[id][tag[id]]++;
}
tag[id]=0;
}
}
int query(int a,int b,int c){
// cdbg("q",a,b,c);
int res=0;
int id=getId(a);
if(tag[id])res+=tag[id]==c?(min(b+1,B*id+B)-a):0;
else for(int i=id*B;i<=id*B+B-1;i++){
if(i>=a&&i<=b)res+=v[i]==c;
}
// cdbg(B,id,getId(b),res);
for(int i=id+1;i<getId(b);i++){
if(tag[i]==c)res+=B;
else if(!tag[i]) res+=vb[i][c];
}
// cdbg(res);
id=getId(b);
if(id!=getId(a)){
if(tag[id])res+=tag[id]==c?(b-max(a-1,B*id-1)):0;
else for(int i=id*B;i<=id*B+B-1;i++){
if(i>=a&&i<=b)res+=v[i]==c;
}
}
return res;
}
void build(){
for(int i=0;i<n;i++){
vb[getId(i)][v[i]]++;
}
}
}using namespace BD;
int b[N];
int tot;
signed main(){
n=rd;
int Q=rd;
B=sqrt(n)+1;
for(int i=0;i<n;i++){
b[++tot]=v[i]=rd;
}
for(int i=1;i<=Q;i++){
q[i]={rd,rd,rd,rd};
if(q[i].op==1)b[++tot]=q[i].c;
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
for(int i=0;i<n;i++)v[i]=lower_bound(b+1,b+tot+1,v[i])-b;
build();
for(int i=1;i<=Q;i++){
int op=q[i].op,a=q[i].a,qb=q[i].b,c=q[i].c;
if(op==1){
c=lower_bound(b+1,b+tot+1,c)-b;
change(a,qb,c);
}else{
// int loc=c;
int loc=lower_bound(b+1,b+tot+1,c)-b;
if(b[loc]!=c)cout<<0<<endl;
else
cout<<query(a,qb,loc)<<endl;
}
}
}
题单¶
整数分块（数论分块）¶
题目描述 给定n，求下列表达式的值： \(\sum_{i=1}^{n}\left[\frac{n}{i}\right]\)
\(n\in[1,10^{12}]\)
void solve(){
int n=rd;
int ans=0;
for(int i=1,nxti;i<=n;i=nxti+1){
nxti=n/(n/i);
ans+=(nxti-i+1)*(n/i);
}
cout<<ans<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
根号分治¶
例题 #1 作业¶
内存限制：256 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
题目描述
1：在人物集合 S 中加入一个新的程序员，其代号为 X,保证 X 在当前集合中不存在。
2：在当前的人物集合中询问程序员的mod Y 最小的值。
输入格式
第一行为用空格隔开的一个个正整数 N。
接下来有 N 行，若该行第一个字符为“A” ，则表示操作 1；若为“B”，表示操作 2；
其中 对于 100%的数据：N≤100000， 1≤X,Y≤300000，保证第二行为操作 1。
输出格式
对于操作 2，每行输出一个合法答案
对\(≤\sqrt(M)\)和 \(>\sqrt(M)\)的询问设计不同的算法。
// Problem: E. 作业
// Contest: LibreOJ - S
// URL: http://www.nfls.com.cn:20035/contest/2100/problem/5
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
// #define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
const int B=sqrt(300000);
set<int> st;
int ans[B+5];
int mx;
void insert(int x){
mx=max(mx,x);
for(int i=1;i<=B;i++){
ans[i]=min(ans[i],x%i);
}
st.insert(x);
}
int query(int x){
// cdbg(x,B);
if(x<=B)return ans[x];
int res=INF;
for(int i=0;i*x<=mx;i++){
int t=*st.lower_bound(i*x);
res=min(res,t%x);
}
return res;
}
signed main(){
memset(ans,0x3f,sizeof ans);
int n=rd;
while(n--){
string op;
cin>>op;
int a=rd;
if(op[0]=='A'){
insert(a);
}else{
cout<<query(a)<<endl;
}
}
}