当前位置：首页 > news >正文

红杭州网站建设品牌网站建设公司

news 2025/8/8 14:06:31

红杭州网站建设,品牌网站建设公司,北京房地产最新消息,web管理系统本期是数列分块入门。其中的大部分题目来自hzwer在LOJ上提供的数列分块入门系列。 Blog:here (其实是对之前分块的 blog 的整理补充) sto hzwer orz %%% [转载] ---------------------------------------------------------------------------------…

本期是数列分块入门。其中的大部分题目来自hzwer在LOJ上提供的数列分块入门系列。

Blog:here (其实是对之前分块的 blog 的整理补充) sto hzwer orz %%% [转载]

------------------------------------------------------------------------------------------------------------------------

分块

我举个例子来说分块。

在一个学校里，有很多班级，而每一个班级就是一个块。

假设某天校长想知道一个班考试的总分，直接查询即可。那如果要查询 1 班的 30 号到 10 班的 20 号呢？对于完整的班级，直接查询；不完整的暴力。

那什么时候这个算法时间复杂度最低呢？答：当块的长度为 $\sqrt n$ 时。

而这就是分块。

例题

LOJ-P6277:

我们每 $m$ 个元素个元素分为一块，共有 $\frac{n}{m}$ 块，以及区间两侧的两个不完整的块。这两个不完整的块中至多 $2m$ 个元素。我们给每个块设置一个 $tag$ （就是记录这个块中元素一起加了多少），每次操作对每个整块直接 $\Theta (1)$ 标记，而不完整的块元素较少，暴力修改元素的值。

这样，每次询问时返回元素的值加上其所在块的加法标记即可。

时间复杂度 $\Theta (\frac{n}{m})+\Theta (m)$ 。根据均值不等式，当 $m$ 取 $\sqrt{n}$ 时总复杂度最低。

#include <bits/stdc++.h>
using namespace std;
const int maxn=50005;
int a[maxn],idx[maxn],tag[maxn],tot;
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++)a[i]+=c;if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)a[i]+=c;}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
int main(){int n;cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)idx[i]=(i-1)/tot+1;for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==1)cout<<a[r]+tag[idx[r]]<<endl;}return O;
}

LOJ-P6278:

我们先来思考只有询问操作的情况，不完整的块枚举统计即可；而要在每个整块内寻找小于一个值的元素数，于是我们不得不要求块内元素是有序的，这样就能使用二分法对块内查询，需要预处理时每块做一遍排序，复杂度 $\Theta (n\: log\: n)$ ，每次查询在 $\sqrt{n}$ 个块内二分，以及暴力 $2 \sqrt{n}$ 个元素，总复杂度 $\Theta (n\: log\: n+n\sqrt{n}\:\: log\: \sqrt{n})$ 。

那么区间加怎么办呢？套用第一题的方法，维护一个加法标记，略有区别的地方在于，不完整的块修改后可能会使得该块内数字乱序，所以头尾两个不完整块需要重新排序。在加法标记下的询问操作，块外还是暴力，查询小于 $(x-tag)$ 的元素个数，块内用 $(x-tag)$ 作为二分的值即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=50005;
int a[maxn],idx[maxn],tag[maxn],tot,n;
vector<int> block[505];
void reset(int x){block[x].clear();for(int i=(x-1)*tot+1;i<=min(x*tot,n);i++)block[x].push_back(a[i]);sort(block[x].begin(),block[x].end());
}
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++)a[i]+=c;reset(idx[l]);if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)a[i]+=c;reset(idx[r]);}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
int query(int l,int r,int c){int ans=0;for(int i=l;i<=min(idx[l]*tot,r);i++){if(a[i]+tag[idx[l]]<c)ans++;}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){if(a[i]+tag[idx[r]]<c)ans++;}}for(int i=idx[l]+1;i<=idx[r]-1;i++)ans+=lower_bound(block[i].begin(),block[i].end(),c-tag[i])-block[i].begin();return ans;
}
int main(){cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;block[idx[i]].push_back(a[i]);}for(int i=1;i<=idx[n];i++)sort(block[i].begin(),block[i].end());for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==1)cout<<query(l,r,c*c)<<endl;}return O;
}

LOJ-P6279:

接着第二题的解法，其实只要把块内查询的二分稍作修改即可。

不过这题其实想表达：可以在块内维护其它结构使其更具有拓展性，比如放一个set，这样如果还有插入、删除元素的操作，会更加的方便。

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000S;
int a[maxn],idx[maxn],tag[maxn],tot=1000;
set<int> st[10S];
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++){st[idx[l]].erase(a[i]);a[i]+=c;st[idx[l]].insert(a[i]);}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){st[idx[r]].erase(a[i]);a[i]+=c;st[idx[r]].insert(a[i]);}}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
int query(int l,int r,int c){int ans=-1;for(int i=l;i<=min(idx[l]*tot,r);i++){int val=a[i]+tag[idx[l]];if(val<c)ans=max(val,ans);}if(idx[l]!=idx[r]){     for(int i=(idx[r]-1)*tot+1;i<=r;i++){int val=a[i]+tag[idx[r]];if(val<c)ans=max(val,ans);}}for(int i=idx[l]+1;i<=idx[r]-1;i++){int x=c-tag[i];set<int>::iterator itr=st[i].lower_bound(x);if(itr==st[i].begin())continue;--itr;ans=max(ans,*itr+tag[i]);}return ans;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;st[idx[i]].insert(a[i]);}for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==1)cout<<query(l,r,c)<<endl;}return 0;
}

LOJ-P6280:

这题的询问变成了区间上的询问，不完整的块还是暴力；而要想快速统计完整块的答案，需要维护每个块的元素和，先要预处理一下。

考虑区间修改操作，不完整的块直接改，顺便更新块的元素和；完整的块类似之前标记的做法，直接根据块的元素和所加的值计算元素和的增量。

#include <bits/stdc++.h>
using namespace std;
int idx[50005],tot;
long long a[50005],tag[50005],sum[50005];
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++){a[i]+=c;sum[idx[l]]+=c;}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){a[i]+=c;sum[idx[r]]+=c;}}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
long long query(int l,int r){long long ans=0;for(int i=l;i<=min(idx[l]*tot,r);i++)ans+=a[i]+tag[idx[l]];if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)ans+=a[i]+tag[idx[r]];}for(int i=idx[l]+1;i<=idx[r]-1;i++)ans+=sum[i]+tot*tag[i];return ans;
}
int main(){int n;cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;sum[idx[i]]+=a[i];}for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c; if(opt==O)change(l,r,c);if(opt==1)cout<<query(l,r)%(c+1)<<endl;}return 0;
}

LOJ-P6281:

稍作思考可以发现，开方操作比较棘手，主要是对于整块开方时，必须要知道每一个元素，才能知道他们开方后的和，也就是说，难以快速对一个块信息进行更新。

看来我们要另辟蹊径。不难发现，这题的修改就只有下取整开方，而一个数经过几次开方之后，它的值就会变成 $0$ 或者 $1$ 。

如果每次区间开方只不涉及完整的块，意味着不超过 $2\sqrt{n}$ 个元素，直接暴力即可。

如果涉及了一些完整的块，这些块经过几次操作以后就会都变成 $0$ 或 $1$ ，于是我们采取一种分块优化的暴力做法，只要每个整块暴力开方后，记录一下元素是否都变成了 $0$ 或 $1$ ，区间修改时跳过那些全为 $0$ 或 $1$ 的块即可。

这样每个元素至多被开方不超过 $4$ 次，显然复杂度没有问题。

#include <bits/stdc++.h> 
using namespace std;
int a[50005],sum[50005],idx[50005],tot;
bool flag[50005];
void solve(int x){if(flag[x])return;flag[x]=1;sum[x]=0;for(int i=(x-1)*tot+1;i<=x*tot;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){for(int i=l;i<=min(idx[l]*tot,r);i++){sum[idx[l]]-=a[i];a[i]=sqrt(a[i]);sum[idx[l]]+=a[i];}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){sum[idx[r]]-=a[i];a[i]=sqrt(a[i]);sum[idx[r]]+=a[i];}}for(int i=idx[l]+1;i<=idx[r]-1;i++)solve(i);
}
int query(int l,int r){int ans=0;for(int i=l;i<=min(idx[l]*tot,r);i++)ans+=a[i];if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)ans+=a[i];}for(int i=idx[l]+1;i<=idx[r]-1;i++)ans+=sum[i];return ans;
}
int main(){int n;cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;sum[idx[i]]+=a[i];}for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==l)cout<<query(l,r)<<endl;}return 0;
}

LOJ-P6284:

区间修改没有什么难度，这题难在区间查询比较奇怪，因为权值种类比较多，似乎没有什么好的维护方法。

模拟一些数据可以发现，询问后一整段都会被修改，几次询问后数列可能只剩下几段不同的区间了。

我们思考这样一个暴力，还是分块，维护每个分块是否只有一种权值，区间操作的时候，对于同权值的一个块就 $\Theta(1)$ 统计答案，否则暴力统计答案，并修改标记，不完整的块也暴力。

这样看似最差情况每次都会耗费 $\Theta(n)$ 的时间，但其实可以这样分析：

假设初始序列都是同一个值，那么查询是 $\Theta(\sqrt n)$ ，如果这时进行一个区间操作，它最多破坏首尾2个块的标记，所以只能使后面的询问至多多2个块的暴力时间，所以均摊每次操作复杂度还是 $\Theta(\sqrt{n})$ 。换句话说，要想让一个操作耗费 $\Theta(n)$ 的时间，要先花费 $\sqrt{n}$ 个操作对数列进行修改。初始序列不同值，经过类似分析后，就可以放心的暴力啦。

#include <bits/stdc++.h>
using namespace std;
int a[maxn],block[maxn],tag[maxn],n,s;
void reset(int x){if(tag[x]==-1)return;for(int i=(x-1)*s+1;i<=s*x;i++)a[i]=tag[x];tag[x]=-1;
}
int query(int l,int r,int c){    int ans=0;reset(block[l]);for(int i=l;i<=min(block[l]*s,r);i++){if(a[i]!=c)a[i]=c;elseans++;}if(block[l]!=block[r]){reset(block[r]);for(int i=(block[r]-1)*s+1;i<=r;i++){if(a[i]!=c)a[i]=c;elseans++;}}for(int i=block[l]+1;i<=block[r]-1;i++){if(tag[i]!=-1){if(tag[i]!=c)tag[i]=c;elseans+=s;}else{for(int j=(i-1)*s+1;j<=i*s;j++){if(a[j]!=c)a[j]=c;elseans++;}tag[i]=c;}}return ans;
}
int main(){memset(tag,-1,sizeof(tag));int n;cin>>n;s=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)block[i]=(i-1)/s+1;for(int i=1;i<=n;i++){int l,r,c;cin>>l>>r>>c;cout<<query(l,r,c)<<endl;}return 0;
}

HDU 5057:

分块板题。

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int v[maxn][15],tag[320][15][15],a[maxn];
void update(int x,int y,int z){for(int d=1;d<=10;d++){v[x][d]=y%10;tag[x/S][d][y%10]+=z;y/=10;}
}
int query(int l,int r,int d,int p){int L=l/S,R=r/S,res=0;if(L==R){for(int i=l;i<=r;i++)res+=(v[i][d]==p);}else{for(int i=l;i<(L+1)*S;i++)res+=(v[i][d]==p);for(int i=R*S;i<=r;i++)res+=(v[i][d]==p);for(int i=L+1;i<R;i++)res+=tag[i][d][p];}return res;
}
int main(){int t;cin>>t;while(t--){memset(tag,0,sizeof(tag));memset(v,0,sizeof(v));int n,m;cin>>n>>m;S=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];update(i,a[i],1);}while(m--){char op;cin>>op;if(op=='S'){int x,y;cin>>x>>y;update(x,a[x],-1);update(x,y,1);a[x]=y;}else{int l,r,d,p;cin>>l>>r>>d>>p;cout<<query(l,r,d,p)<<endl;}}}return 0;
}