分块的思想可以解决很多问题，比如区间更新，区间求和/单点询问，当然这些问题也可以用线段树或者树状数组解决（而且线段树的时间复杂度相对较低）。
对于某些问题，比如“区间加法，询问区间内小于某个值x的最大元素”，分块是比较方便的。
LOJ 6277 数列分块入门1
区间加法，单点询问。
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,l,r,k,bl,opt,a[N],b[N],f[N];
void add(int l,int r,int k)
{
for(int i=l;i<=min(r,b[l]*bl);i++)
a[i]+=k;
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
a[i]+=k;
for(int i=b[l]+1;i<=b[r]-1;i++)
f[i]+=k;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
bl=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=(i-1)/bl+1;
}
for(int i=1;i<=n;i++)
{
cin>>opt>>l>>r>>k;
if(opt==0)add(l,r,k);
else printf("%d\n",a[r]+f[b[r]]);
}
return 0;
}
LOJ 6278 数列分块入门2
区间加法，询问区间内小于某个值x的元素个数。
滚动数组 g[ i ][ j ] 表示第 i 块的第 j 个元素，维护这个数组，使其升序排列，便于之后二分查找。
对最左块和最右块的部分元素进行区间加法后，可能会打破原来的升序排列，必须重新排序最左块和最右块。
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
vector<int>g[510];
int n,l,r,k,bl,opt,a[N],b[N],f[N];
void resort(int num)//对第num块内重新排序
{
g[num].clear();
for(int i=(num-1)*bl+1;i<=num*bl;i++)
g[num].push_back(a[i]);
sort(g[num].begin(),g[num].end());
}
void add(int l,int r,int k)
{
for(int i=l;i<=min(r,b[l]*bl);i++)//暴力更新最左块内部分元素
a[i]+=k;
resort(b[l]);//重新排序最左块
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)//暴力更新最右块内部分元素
a[i]+=k;
resort(b[r]);//重新排序最右块
for(int i=b[l]+1;i<=b[r]-1;i++)
f[i]+=k;//第i块加上懒标记，之后查询的时候块内元素再加上懒标记
}
int query(int l,int r,int k)
{
int s=0;
for(int i=l;i<=min(r,b[l]*bl);i++)
if(a[i]+f[b[l]]<k)s++;
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
if(a[i]+f[b[r]]<k)s++;
for(int i=b[l]+1;i<=b[r]-1;i++)
{
int tmp=lower_bound(g[i].begin(),g[i].end(),k-f[i])-g[i].begin();//二分查找第i块内大于等于k-f[i]的第一个元素下标
s+=tmp;
}
return s;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
bl=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=(i-1)/bl+1;
g[b[i]].push_back(a[i]);
}
for(int i=1;i<=b[n];i++)
sort(g[i].begin(),g[i].end());
for(int i=1;i<=n;i++)
{
cin>>opt>>l>>r>>k;
if(opt==0)add(l,r,k);
else printf("%d\n",query(l,r,k*k));
}
return 0;
}
LOJ 6279 数列分块入门3
区间加法，询问区间内小于某个值x的前驱（比其小的最大元素）。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[510];
int n,l,r,k,bl,opt,a[N],b[N],f[N];
void resort(int num)
{
g[num].clear();
for(int i=(num-1)*bl+1;i<=num*bl;i++)
g[num].push_back(a[i]);
sort(g[num].begin(),g[num].end());
}
void add(int l,int r,int k)
{
for(int i=l;i<=min(r,bl*b[l]);i++)
a[i]+=k;
resort(b[l]);
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
a[i]+=k;
resort(b[r]);
for(int i=b[l]+1;i<=b[r]-1;i++)
f[i]+=k;
}
int query(int l,int r,int k)
{
int mx=-1;
for(int i=l;i<=min(r,bl*b[l]);i++)
if(a[i]+f[b[l]]<k)mx=max(mx,a[i]+f[b[l]]);
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
if(a[i]+f[b[r]]<k)mx=max(mx,a[i]+f[b[r]]);
for(int i=b[l]+1;i<=b[r]-1;i++)
{
int tmp=lower_bound(g[i].begin(),g[i].end(),k-f[i])-g[i].begin();
if(tmp>=1)mx=max(mx,g[i][tmp-1]+f[i]);
}
return mx;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
bl=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=(i-1)/bl+1;
g[b[i]].push_back(a[i]);
}
for(int i=1;i<=b[n];i++)
sort(g[i].begin(),g[i].end());
for(int i=1;i<=n;i++)
{
cin>>opt>>l>>r>>k;
if(opt==0)add(l,r,k);
else printf("%d\n",query(l,r,k));
}
return 0;
}
LOJ 6280 数列分块入门4
区间加法，区间求和。
与线段树类似，要开一个懒标记数组f[i] (表示第i块内所有元素本来要加上的值)，查询的时候再分块把懒标记加上。
sum[i]表示第i块的和，f[i]表示第i块的懒标记。本题的懒标记数组和sum数组必须要用long long。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,l,r,k,bl,opt,a[N],b[N];
ll f[N],sum[N];//sum[i]表示第i块的和，f[i]表示第i块的懒标记
void add(int l,int r,int k)
{
for(int i=l;i<=min(r,b[l]*bl);i++)
{a[i]+=k;sum[b[l]]+=k;}
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
{a[i]+=k;sum[b[r]]+=k;}
for(int i=b[l]+1;i<=b[r]-1;i++)
f[i]+=k;
}
ll query(int l,int r,int mod)
{
ll s=0;
for(int i=l;i<=min(r,b[l]*bl);i++)
s+=(a[i]+f[b[l]])%mod;
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
s+=(a[i]+f[b[r]])%mod;
for(int i=b[l]+1;i<=b[r]-1;i++)
s+=(sum[i]+f[i]*bl)%mod;
return s%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
bl=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=(i-1)/bl+1;
sum[b[i]]+=a[i];
}
for(int i=1;i<=n;i++)
{
cin>>opt>>l>>r>>k;
if(opt==0)add(l,r,k);
else printf("%d\n",query(l,r,k+1));
}
return 0;
}
LOJ 6281 数列分块入门5
区间开方，区间求和。
int范围内(x<2^31)，一个数x，如果x<1，则开方一次后向下取整为0；如果x>=1，则最多被开方5次后向下取整为1。
无论x大于1还是小于1，开方次数大于等于5次后再开方，值是不变的。
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,l,r,k,bl,opt,a[N],b[N],cnt[N],sum[N];//sum[i]记录第i块的和，cnt[i]表示第i块的开方次数
void update(int l,int r)
{
if(cnt[b[l]]<5)
for(int i=l;i<=min(r,bl*b[l]);i++)
{
sum[b[l]]-=a[i];
a[i]=(int)sqrt(a[i]);
sum[b[l]]+=a[i];
}
if(cnt[b[r]]<5&&b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
{
sum[b[r]]-=a[i];
a[i]=(int)sqrt(a[i]);
sum[b[r]]+=a[i];
}
for(int i=b[l]+1;i<=b[r]-1;i++)//遍历中间的整块
{
if(cnt[i]<5)
{
for(int j=(i-1)*bl+1;j<=i*bl;j++)//遍历第i块内的所有元素a[j]，进行开方，更新a[j]和sum[i]
{
sum[i]-=a[j];
a[j]=(int)sqrt(a[j]);
sum[i]+=a[j];
}
}
cnt[i]++;//第i块的开方次数+1
}
}
int query(int l,int r)
{
int s=0;
for(int i=l;i<=min(r,b[l]*bl);i++)
s+=a[i];
if(b[l]!=b[r])
for(int i=(b[r]-1)*bl+1;i<=r;i++)
s+=a[i];
for(int i=b[l]+1;i<=b[r]-1;i++)
s+=sum[i];
return s;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
bl=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=(i-1)/bl+1;
sum[b[i]]+=a[i];
}
for(int i=1;i<=n;i++)
{
cin>>opt>>l>>r>>k;
if(opt==0)update(l,r);
else printf("%d\n",query(l,r));
}
return 0;
}
Comments | NOTHING