算法查漏补缺 #1 分块
编辑什么是分块
用于实现区间更新与区间查询的数据结构，
可用于骗分
。
相较于BIT、线段树等数据结构虽速度较慢，但更加灵活，多种问题均可转化为分块
分块的具体实现（单点修改）
使用查询区间最大值的实现来举例：
定义数组 a_i 为原始输入，b_i 代表 i 号元素对应的块编号，bm_k 代表 k 号块对应的块内最大值。
要对于一个区间 [l,r] 进行区间查询，首先需要注意** l 与 r 是否在同一块内**。如果不在同一块内，首先记录左侧端点所在块号 b_l
与右侧端点所在块号 b_r ，遍历从 l 到所在块号为 b_l 的最后一个元素，右端点附近处理方式同理。接下来遍历中间块，即块编号在 [b_l+1,b_r-1] 中的所有块的 bm 。
需要注意的是，以上操作仅支持单点修改，未考虑区间修改。
代码实现（单点修改）
块编号预处理/输入处理
int B=sqrt(n)+1; // 块总数
for(int i=1;i<=n;i++) b[i]=(i-1)/B+1;
for(int i=1;i<=n;i++){
cin>>a[i];
bm[b[i]]=max(bm[b[i]],a[i]);
}
其中我们令总块数为 \sqrt{n} 。可以证明，取块数为 \sqrt{n} 时最优，下面给出简单证明：
考虑最坏情况，即遍历一个块长度的离散元素和 \frac nB 个块，时间复杂度为 B+\frac nB 。考虑基本不等式，显然 B > 0 ，则 B+\frac nB 在 B =\frac nB 即 B=\sqrt{n} 时取得最小值。
区间查询
int rmq(int l,int r){
int res=-INF;
if(b[l]==b[r]){
res=*max_element(a+1+l,a+1+r);
return res;
}
else{
for(int i=l;b[i]==b[l];i++) res=max(res,a[i]);
for(int i=b[l]+1;i<=b[r]-1;i++) res=max(res,bm[i]);
for(int i=r;b[i]==b[r];i--) res=max(res,a[i]);
}
return res;
}
实现区间修改
参考线段树中的 lazytag ，实现区间修改，定义 c_k 为 k 号块的偏移量。
每次区间修改类似于区间查询，先判断是否在同一块，再修改两边元素和中间的 lazytag 。
区间修改代码实现
区间修改
int add(int l,int r,int k){
int tag;
if(b[l]==b[r]){
tag=c[b[l]];
for(int i=l;i<=r;i++){
a[i]+=k;
bm[b[i]]=max(bm[b[i]],a[i]+tag);
}
return ;
}
else{
tag=c[b[l]];
for(int i=l;b[i]==b[l];i++){
a[i]+=k;
bm[b[i]]=max(bm[b[i]],a[i]+tag);
}
tag=c[b[r]];
for(int i=r;b[i]==b[r];i--){
a[i]+=k;
bm[b[i]]=max(bm[b[i]],a[i]+tag);
}
for(int i=b[l]+1;i<=b[r]-1;i++) c[i]+=k,bm[i]+=k; // 不要忘记修改区间最大值！
}
}
区间查询（添加 lazytag）
int rmq(int l,int r){
int res=-INF;
int tag;
if(b[l]==b[r]){
tag=c[b[l]];
res=*max_element(a+1+l,a+1+r)+tag;
return res;
}
else{
tag=c[b[l]];
for(int i=l;b[i]==b[l];i++) res=max(res,a[i]+tag);
tag=c[b[r]];
for(int i=r;b[i]==b[r];i--) res=max(res,a[i]+tag);
for(int i=b[l]+1;i<=b[r]-1;i++) res=max(res,bm[i]); // 修改时已经加过了，不要重复加
}
return res;
}
例题1（区间内特定值域内元素计数）
长城上共有n个防御塔。第i个防御塔的防御力为 a_i 。在你的作战指挥部里，你正在模拟m种轰炸方式。第j种轰炸方式的攻击范围从第 l_j 个防御塔炸到第 r_j 个，攻击力为 k_j 。其中防御力小于等于 k_j 的塔都会被摧毁。请对每种轰炸方式，计算能炸毁几个塔。
思路分析
对于这种问题，我们可以考虑块内排序后再在块内进行二分查找。由于每个块的处理时间发生改变，我们的块数需要重新计算。
每个分块查询进行一次二分，单个分块的时间复杂度为 O(\log B) ，共有 B 块，最坏情况为 B + \frac {n \log B}B 。则有 B=\sqrt{n \log B} \approx \sqrt{n \log n} 。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+9;
ll n,m;
ll a[N],b[N],as[N];
ll lB[N],rB[N]; // k号块的左右端点下表
ll B;
int query(int l,int r,int k){
ll cnt=0;
if(b[l]==b[r]){
for(int i=l;i<=r;i++){
if(a[i]<=k) cnt++;
}
return cnt;
}
else{
for(int i=l;b[i]==b[l];i++) if(a[i]<=k) cnt++;
for(int i=r;b[i]==b[r];i--) if(a[i]<=k) cnt++;
for(int i=b[l]+1;i<=b[r]-1;i++){
// 寻找第一个大于的，所以使用upper_bound
cnt+=upper_bound(as+lB[i],as+rB[i]+1,k)-as-lB[i];
}
return cnt;
}
}
int main(){
cin>>n>>m;
B=sqrt(log2(n)*n)+1;
for(int i=1;i<=n;i++) b[i]=(i-1)/B+1;
for(int i=1;i<=b[n]-1;i++){ // 这里要对最后一块单独处理
lB[i]=(i-1)*B+1;
rB[i]=B*i;
}
for(int i=1;i<=n;i++){
cin>>a[i];
as[i]=a[i];
}
for(int i=1;i<=b[n];i++) sort(as+lB[i],as+rB[i]+1); // 块内排序
for(int i=1;i<=m;i++){
ll l,r,k;
cin>>l>>r>>k;
cout<<query(l,r,k)<<' ';
}
return 0;
}
例题2（实时排名）
大赛共 n 位选手。决赛只有一题一次网络提交机会，n 位选手依次提交，第 n 个提交的选手显示出得分为 x_i ，即刻他的分数就会记录到得分排行榜上，对于每个选手请你求出他提交的时刻是当时第几名？可能名次并列。
输入一行为正整数n，2<=n<=200000。接着一行为n个非负整数，第i个数为xi，均不超过10000
这题我们需要转变思路，不一定需要对选手编号进行分块，而是对分数进行分块。但是这需要数据的最大值较小，观察到这道题中 x_i 均不超过10000，因此可对分数进行分块。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int S=10001; //将分数全部+1，保证从1开始
const int B=sqrt(S)+1;
const int N=10009;
int n;
int x[N],b[N],cnt[N],bc[N];
int main(){
cin>>n;
for(int i=1;i<=S;i++) b[i]=(i-1)/B+1;
for(int i=1;i<=n;i++){
int s;
cin>>s;
s++;
cnt[s]++,bc[b[s]]++;
int ans=0;
for(int j=b[s]+1;j<=b[S];j++){
ans+=bc[j];
}
int rB=min(S,b[s]*B);
for(int j=s+1;j<=rB;j++){
ans+=cnt[j];
}
cout<<ans+1<<' '; //排名要+1！
}
return 0;
}
- 0
- 0
-
分享