lzx's blog 分块是什么？
就是把一个序列分成若干块，预处理一部分信息然后保存。
对比线段树、树状数组，分块虽然更慢，但是空间用量少、直观。
适合骗分（确信）
一道题目来说明:数列分块 4
我们可以把序列分成若干个长度为 $\lfloor \sqrt{N} \rfloor$ 的块，如果不能分完，再将剩下的新开一块放入。
我们先设 $pr = \lfloor \sqrt{N} \rfloor$
对于除最后一块以外的块，第 $i$ 块左端点 $st_i$ 为 $(i-1)·pr+1$，右端点 $ed_i$ 为 $i·pr$
最后一块左端点 $st_{pr+1} $为 $ed_{pr}+1$，右端点 $ed_{pr+1}$ 则为 $n$
如下图
| 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 块序号 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 |
我们可以预处理出 $sum$ 数组，其中 $sum_i$ 表示第 $i$ 块的和。
我们还要使用 $d$ 数组，代表每一块的增量标记，初始所有 $d_i = 0$
设 $p$ 为 $l$ 所在的块，$q$ 为 $r$ 所在的块
对于 opt = 0
我们分类讨论一下
- $l$ 和 $r$ 处于同一块内，直接暴力将 $a_l,a_{l+1},\dots,a_{r-1},a_{r}$ 各加上 $c$ 即可，同时将 $sum_{p} += c \times (r-l+1)$
- 对于第 $p+1 \sim q-1$ 块，直接将增量标记 $d_i += c$ 并 $sum_i += c \times (ed_i - st_i +1)$ ;第 $p$ 块和 $q$ 块由于不完整与第 $1$ 种方案类似处理即可
对于 opt = 1
再次分类讨论
- $l$ 和 $r$ 处于同一块内，直接暴力算 $\sum_{i=l}^r a_i + d_p \times (r-l+1)$ 即可
- 对于第 $p+1 \sim q-1$ 块直接累加 $sum_i$ 即可； $p$ 块和 $q$ 块由于不完整与第 $1$ 种方案类似处理累加即可
数列分块 1
数列分块 $4$ 的削弱版，查询输出 $a_i + d_p$ 即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010],pr,st[1010],ed[1010],pos[100010],sum[1010],d[1010];
void change(int l,int r,int c)
{
int p=pos[l],q=pos[r];
if(p==q)
{
for(int i=l;i<=r;i++)
{
a[i]+=c;
}
sum[p]+=c*(r-l+1);
}
else
{
for(int i=p+1;i<=q-1;i++)
{
sum[i]+=(ed[i]-st[i]+1)*c;
d[i]+=c;
}
for(int i=l;i<=ed[p];i++)
{
a[i]+=c;
}
sum[p]+=c*(ed[p]-l+1);
for(int i=st[q];i<=r;i++)
{
a[i]+=c;
}
sum[q]+=c*(r-st[q]+1);
}
}
int query(int l)
{
return a[l]+d[pos[l]];
}
signed main()
{
cin>>n;
m=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
pr=sqrt(n);
for(int i=1;i<=pr;i++)
{
st[i]=(i-1)*pr+1;
ed[i]=i*pr;
}
if(ed[pr]<n)
{
pr++;
st[pr]=ed[pr-1]+1;
ed[pr]=n;
}
for(int i=1;i<=pr;i++)
{
for(int j=st[i];j<=ed[i];j++)
{
pos[j]=i;
sum[i]+=a[j];
}
}
for(int i=1;i<=m;i++)
{
int op,l,r,c;
cin>>op>>l>>r>>c;
if(op==0)
{
change(l,r,c);
}
else if(op==1)
{
cout<<query(r)<<"\n";
}
}
return 0;
}数列分块 2
对于两端不完整的暴力
中间每块排序然后二分查找第一个 $\ge c^2$ 的即可，累加前面一部分的个数即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010],pr,st[1010],ed[1010],pos[100010],sum[1010],d[1010];
vector <int> b[1010];
void upd(int x)
{
b[x].clear();
for(int i=st[x];i<=ed[x];i++)
{
b[x].push_back(a[i]);
}
sort(b[x].begin(),b[x].end());
}
void change(int l,int r,int c)
{
int p=pos[l],q=pos[r];
if(p==q)
{
for(int i=l;i<=r;i++)
{
a[i]+=c;
}
upd(p);
}
else
{
for(int i=p+1;i<=q-1;i++)
{
d[i]+=c;
}
for(int i=l;i<=ed[p];i++)
{
a[i]+=c;
}
upd(p);
for(int i=st[q];i<=r;i++)
{
a[i]+=c;
}
upd(q);
}
}
int query(int l,int r,int c)
{
int p=pos[l],q=pos[r];
int ans=0;
if(p==q)
{
for(int i=l;i<=r;i++)
{
if(a[i]+d[p]<c) ans++;
}
}
else
{
for(int i=p+1;i<=q-1;i++)
{
int l=lower_bound(b[i].begin(),b[i].end(),c-d[i])-b[i].begin();
ans+=l;
}
for(int i=l;i<=ed[p];i++)
{
if(a[i]+d[p]<c) ans++;
}
for(int i=st[q];i<=r;i++)
{
if(a[i]+d[q]<c) ans++;
}
}
return ans;
}
signed main()
{
cin>>n;
m=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
pr=sqrt(n);
for(int i=1;i<=pr;i++)
{
st[i]=(i-1)*pr+1;
ed[i]=i*pr;
}
if(ed[pr]<n)
{
pr++;
st[pr]=ed[pr-1]+1;
ed[pr]=n;
}
for(int i=1;i<=pr;i++)
{
for(int j=st[i];j<=ed[i];j++)
{
pos[j]=i;
}
}
for(int i=1;i<=pr;i++)
{
upd(i);
}
for(int i=1;i<=m;i++)
{
int op,l,r,c;
cin>>op>>l>>r>>c;
if(op==0)
{
change(l,r,c);
}
else if(op==1)
{
cout<<query(l,r,c*c)<<"\n";
}
}
return 0;
}数列分块 3
与 数列分块 2 差不多
两边不完整的还是暴力判断
中间排序后依旧用二分找每个块里 $< c$ 且最大的
然后打擂台即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010],pr,st[1010],ed[1010],pos[100010],sum[1010],d[1010];
vector <int> b[1010];
void upd(int x)
{
b[x].clear();
for(int i=st[x];i<=ed[x];i++)
{
b[x].push_back(a[i]);
}
sort(b[x].begin(),b[x].end());
}
void change(int l,int r,int c)
{
int p=pos[l],q=pos[r];
if(p==q)
{
for(int i=l;i<=r;i++)
{
a[i]+=c;
}
upd(p);
}
else
{
for(int i=p+1;i<=q-1;i++)
{
d[i]+=c;
}
for(int i=l;i<=ed[p];i++)
{
a[i]+=c;
}
upd(p);
for(int i=st[q];i<=r;i++)
{
a[i]+=c;
}
upd(q);
}
}
int query(int l,int r,int c)
{
int p=pos[l],q=pos[r];
int ans=-1;
if(p==q)
{
for(int i=l;i<=r;i++)
{
if(a[i]+d[p]<c) ans=max(a[i]+d[p],ans);
}
}
else
{
for(int i=p+1;i<=q-1;i++)
{
int cnt=lower_bound(b[i].begin(),b[i].end(),c-d[i])-b[i].begin();
cnt--;
if(cnt>=0) ans=max(b[i][cnt]+d[i],ans);
}
for(int i=l;i<=ed[p];i++)
{
if(a[i]+d[p]<c) ans=max(a[i]+d[p],ans);
}
for(int i=st[q];i<=r;i++)
{
if(a[i]+d[q]<c) ans=max(a[i]+d[q],ans);
}
}
return ans;
}
signed main()
{
cin>>n;
m=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
pr=sqrt(n);
for(int i=1;i<=pr;i++)
{
st[i]=(i-1)*pr+1;
ed[i]=i*pr;
}
if(ed[pr]<n)
{
pr++;
st[pr]=ed[pr-1]+1;
ed[pr]=n;
}
for(int i=1;i<=pr;i++)
{
for(int j=st[i];j<=ed[i];j++)
{
pos[j]=i;
}
}
for(int i=1;i<=pr;i++)
{
upd(i);
}
for(int i=1;i<=m;i++)
{
int op,l,r,c;
cin>>op>>l>>r>>c;
if(op==0)
{
change(l,r,c);
}
else if(op==1)
{
cout<<query(l,r,c)<<"\n";
}
}
return 0;
}数列分块 4
见最上面举的例子
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010],pr,st[1010],ed[1010],pos[100010],sum[1010],d[1010];
void change(int l,int r,int c)
{
int p=pos[l],q=pos[r];
if(p==q)
{
for(int i=l;i<=r;i++)
{
a[i]+=c;
}
sum[p]+=c*(r-l+1);
}
else
{
for(int i=p+1;i<=q-1;i++)
{
sum[i]+=(ed[i]-st[i]+1)*c;
d[i]+=c;
}
for(int i=l;i<=ed[p];i++)
{
a[i]+=c;
}
sum[p]+=c*(ed[p]-l+1);
for(int i=st[q];i<=r;i++)
{
a[i]+=c;
}
sum[q]+=c*(r-st[q]+1);
}
}
int query(int l,int r)
{
int p=pos[l],q=pos[r];
int ans=0;
if(p==q)
{
for(int i=l;i<=r;i++)
{
ans+=a[i];
}
ans+=d[p]*(r-l+1);
}
else
{
for(int i=p+1;i<=q-1;i++)
{
ans+=sum[i];
}
for(int i=l;i<=ed[p];i++)
{
ans+=a[i];
}
ans+=d[p]*(ed[p]-l+1);
for(int i=st[q];i<=r;i++)
{
ans+=a[i];
}
ans+=d[q]*(r-st[q]+1);
}
return ans;
}
signed main()
{
cin>>n;
m=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
pr=sqrt(n);
for(int i=1;i<=pr;i++)
{
st[i]=(i-1)*pr+1;
ed[i]=i*pr;
}
if(ed[pr]<n)
{
pr++;
st[pr]=ed[pr-1]+1;
ed[pr]=n;
}
for(int i=1;i<=pr;i++)
{
for(int j=st[i];j<=ed[i];j++)
{
pos[j]=i;
sum[i]+=a[j];
}
}
for(int i=1;i<=m;i++)
{
int op,l,r,c;
cin>>op>>l>>r>>c;
if(op==0)
{
change(l,r,c);
}
else if(op==1)
{
cout<<query(l,r)%(c+1)<<"\n";
}
}
return 0;
}数列分块 5
诈骗题
开方最多开 $5$ 次就到 $1$，每开一次就给每块 $tag++$，每块最多 $5$ 次，时间充足
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100010],pr,st[1010],ed[1010],pos[100010],sum[1010],d[1010],tag[1010];
void resum(int x)
{
sum[x]=0;
for(int i=st[x];i<=ed[x];i++)
{
sum[x]+=a[i];
}
}
void kf(int x)
{
if(tag[x]>5) return;
for(int i=st[x];i<=ed[x];i++)
{
a[i]=sqrt(a[i]);
}
resum(x);
}
void change(int l,int r)
{
int p=pos[l],q=pos[r];
if(p==q)
{
for(int i=l;i<=r;i++)
{
a[i]=sqrt(a[i]);
}
resum(p);
}
else
{
for(int i=p+1;i<=q-1;i++)
{
kf(i);
tag[i]++;
}
for(int i=l;i<=ed[p];i++)
{
a[i]=sqrt(a[i]);
}
resum(p);
for(int i=st[q];i<=r;i++)
{
a[i]=sqrt(a[i]);
}
resum(q);
}
}
int query(int l,int r)
{
int p=pos[l],q=pos[r];
int ans=0;
if(p==q)
{
for(int i=l;i<=r;i++)
{
ans+=a[i];
}
}
else
{
for(int i=p+1;i<=q-1;i++)
{
ans+=sum[i];
}
for(int i=l;i<=ed[p];i++)
{
ans+=a[i];
}
for(int i=st[q];i<=r;i++)
{
ans+=a[i];
}
}
return ans;
}
signed main()
{
cin>>n;
m=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
pr=sqrt(n);
for(int i=1;i<=pr;i++)
{
st[i]=(i-1)*pr+1;
ed[i]=i*pr;
}
if(ed[pr]<n)
{
pr++;
st[pr]=ed[pr-1]+1;
ed[pr]=n;
}
for(int i=1;i<=pr;i++)
{
for(int j=st[i];j<=ed[i];j++)
{
pos[j]=i;
sum[i]+=a[j];
}
}
for(int i=1;i<=m;i++)
{
int op,l,r,c;
cin>>op>>l>>r>>c;
if(op==0)
{
change(l,r);
}
else if(op==1)
{
cout<<query(l,r)<<"\n";
}
}
return 0;
}
1 条评论
poor PR