网站的视频怎么下载,wordpress入门,法治建设网站模块,校园网站建设的作用本期是数列分块入门。其中的大部分题目来自hzwer在LOJ上提供的数列分块入门系列。
Blog:here (其实是对之前分块的 blog 的整理补充) sto hzwer orz %%% [转载]
---------------------------------------------------------------------------------…本期是数列分块入门。其中的大部分题目来自hzwer在LOJ上提供的数列分块入门系列。
Blog:here (其实是对之前分块的 blog 的整理补充) sto hzwer orz %%% [转载]
------------------------------------------------------------------------------------------------------------------------
分块
我举个例子来说分块。
在一个学校里有很多班级而每一个班级就是一个块。
假设某天校长想知道一个班考试的总分直接查询即可。那如果要查询 1 班的 30 号到 10 班的 20 号呢对于完整的班级直接查询不完整的暴力。
那什么时候这个算法时间复杂度最低呢答当块的长度为时。
而这就是分块。
例题
LOJ-P6277:
我们每个元素个元素分为一块共有块以及区间两侧的两个不完整的块。这两个不完整的块中至多个元素。我们给每个块设置一个就是记录这个块中元素一起加了多少每次操作对每个整块直接标记而不完整的块元素较少暴力修改元素的值。
这样每次询问时返回元素的值加上其所在块的加法标记即可。
时间复杂度。根据均值不等式当取时总复杂度最低。
#include bits/stdc.h
using namespace std;
const int maxn50005;
int a[maxn],idx[maxn],tag[maxn],tot;
void change(int l,int r,int c){for(int il;imin(idx[l]*tot,r);i)a[i]c;if(idx[l]!idx[r]){for(int i(idx[r]-1)*tot1;ir;i)a[i]c;}for(int iidx[l]1;iidx[r]-1;i)tag[i]c;
}
int main(){int n;cinn;totsqrt(n);for(int i1;in;i)cina[i];for(int i1;in;i)idx[i](i-1)/tot1;for(int i1;in;i){int opt,l,r,c;cinoptlrc;if(opt0)change(l,r,c);if(opt1)couta[r]tag[idx[r]]endl;}return O;
}
LOJ-P6278:
我们先来思考只有询问操作的情况不完整的块枚举统计即可而要在每个整块内寻找小于一个值的元素数于是我们不得不要求块内元素是有序的这样就能使用二分法对块内查询需要预处理时每块做一遍排序复杂度每次查询在个块内二分以及暴力个元素总复杂度。
那么区间加怎么办呢套用第一题的方法维护一个加法标记略有区别的地方在于不完整的块修改后可能会使得该块内数字乱序所以头尾两个不完整块需要重新排序。在加法标记下的询问操作块外还是暴力查询小于的元素个数块内用作为二分的值即可。
#include bits/stdc.h
using namespace std;
const int maxn50005;
int a[maxn],idx[maxn],tag[maxn],tot,n;
vectorint block[505];
void reset(int x){block[x].clear();for(int i(x-1)*tot1;imin(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 il;imin(idx[l]*tot,r);i)a[i]c;reset(idx[l]);if(idx[l]!idx[r]){for(int i(idx[r]-1)*tot1;ir;i)a[i]c;reset(idx[r]);}for(int iidx[l]1;iidx[r]-1;i)tag[i]c;
}
int query(int l,int r,int c){int ans0;for(int il;imin(idx[l]*tot,r);i){if(a[i]tag[idx[l]]c)ans;}if(idx[l]!idx[r]){for(int i(idx[r]-1)*tot1;ir;i){if(a[i]tag[idx[r]]c)ans;}}for(int iidx[l]1;iidx[r]-1;i)anslower_bound(block[i].begin(),block[i].end(),c-tag[i])-block[i].begin();return ans;
}
int main(){cinn;totsqrt(n);for(int i1;in;i)cina[i];for(int i1;in;i){idx[i](i-1)/tot1;block[idx[i]].push_back(a[i]);}for(int i1;iidx[n];i)sort(block[i].begin(),block[i].end());for(int i1;in;i){int opt,l,r,c;cinoptlrc;if(opt0)change(l,r,c);if(opt1)coutquery(l,r,c*c)endl;}return O;
}
LOJ-P6279:
接着第二题的解法其实只要把块内查询的二分稍作修改即可。
不过这题其实想表达可以在块内维护其它结构使其更具有拓展性比如放一个set这样如果还有插入、删除元素的操作会更加的方便。
#include bits/stdc.h
using namespace std;
const int maxn10000S;
int a[maxn],idx[maxn],tag[maxn],tot1000;
setint st[10S];
void change(int l,int r,int c){for(int il;imin(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)*tot1;ir;i){st[idx[r]].erase(a[i]);a[i]c;st[idx[r]].insert(a[i]);}}for(int iidx[l]1;iidx[r]-1;i)tag[i]c;
}
int query(int l,int r,int c){int ans-1;for(int il;imin(idx[l]*tot,r);i){int vala[i]tag[idx[l]];if(valc)ansmax(val,ans);}if(idx[l]!idx[r]){ for(int i(idx[r]-1)*tot1;ir;i){int vala[i]tag[idx[r]];if(valc)ansmax(val,ans);}}for(int iidx[l]1;iidx[r]-1;i){int xc-tag[i];setint::iterator itrst[i].lower_bound(x);if(itrst[i].begin())continue;--itr;ansmax(ans,*itrtag[i]);}return ans;
}
int main(){int n;cinn;for(int i1;in;i)cina[i]; for(int i1;in;i){idx[i](i-1)/tot1;st[idx[i]].insert(a[i]);}for(int i1;in;i){int opt,l,r,c;cinoptlrc;if(opt0)change(l,r,c);if(opt1)coutquery(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 il;imin(idx[l]*tot,r);i){a[i]c;sum[idx[l]]c;}if(idx[l]!idx[r]){for(int i(idx[r]-1)*tot1;ir;i){a[i]c;sum[idx[r]]c;}}for(int iidx[l]1;iidx[r]-1;i)tag[i]c;
}
long long query(int l,int r){long long ans0;for(int il;imin(idx[l]*tot,r);i)ansa[i]tag[idx[l]];if(idx[l]!idx[r]){for(int i(idx[r]-1)*tot1;ir;i)ansa[i]tag[idx[r]];}for(int iidx[l]1;iidx[r]-1;i)anssum[i]tot*tag[i];return ans;
}
int main(){int n;cinn;totsqrt(n);for(int i1;in;i)cina[i];for(int i1;in;i){idx[i](i-1)/tot1;sum[idx[i]]a[i];}for(int i1;in;i){int opt,l,r,c;cinoptlrc; if(optO)change(l,r,c);if(opt1)coutquery(l,r)%(c1)endl;}return 0;
}
LOJ-P6281:
稍作思考可以发现开方操作比较棘手主要是对于整块开方时必须要知道每一个元素才能知道他们开方后的和也就是说难以快速对一个块信息进行更新。
看来我们要另辟蹊径。不难发现这题的修改就只有下取整开方而一个数经过几次开方之后它的值就会变成或者。
如果每次区间开方只不涉及完整的块意味着不超过个元素直接暴力即可。
如果涉及了一些完整的块这些块经过几次操作以后就会都变成或于是我们采取一种分块优化的暴力做法只要每个整块暴力开方后记录一下元素是否都变成了或区间修改时跳过那些全为或的块即可。
这样每个元素至多被开方不超过次显然复杂度没有问题。
#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)*tot1;ix*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 il;imin(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)*tot1;ir;i){sum[idx[r]]-a[i];a[i]sqrt(a[i]);sum[idx[r]]a[i];}}for(int iidx[l]1;iidx[r]-1;i)solve(i);
}
int query(int l,int r){int ans0;for(int il;imin(idx[l]*tot,r);i)ansa[i];if(idx[l]!idx[r]){for(int i(idx[r]-1)*tot1;ir;i)ansa[i];}for(int iidx[l]1;iidx[r]-1;i)anssum[i];return ans;
}
int main(){int n;cinn;totsqrt(n);for(int i1;in;i)cina[i];for(int i1;in;i){idx[i](i-1)/tot1;sum[idx[i]]a[i];}for(int i1;in;i){int opt,l,r,c;cinoptlrc;if(opt0)change(l,r,c);if(optl)coutquery(l,r)endl;}return 0;
}
LOJ-P6284:
区间修改没有什么难度这题难在区间查询比较奇怪因为权值种类比较多似乎没有什么好的维护方法。
模拟一些数据可以发现询问后一整段都会被修改几次询问后数列可能只剩下几段不同的区间了。
我们思考这样一个暴力还是分块维护每个分块是否只有一种权值区间操作的时候对于同权值的一个块就统计答案否则暴力统计答案并修改标记不完整的块也暴力。
这样看似最差情况每次都会耗费的时间但其实可以这样分析
假设初始序列都是同一个值那么查询是如果这时进行一个区间操作它最多破坏首尾2个块的标记所以只能使后面的询问至多多2个块的暴力时间所以均摊每次操作复杂度还是。换句话说要想让一个操作耗费的时间要先花费个操作对数列进行修改。初始序列不同值经过类似分析后就可以放心的暴力啦。
#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)*s1;is*x;i)a[i]tag[x];tag[x]-1;
}
int query(int l,int r,int c){ int ans0;reset(block[l]);for(int il;imin(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)*s1;ir;i){if(a[i]!c)a[i]c;elseans;}}for(int iblock[l]1;iblock[r]-1;i){if(tag[i]!-1){if(tag[i]!c)tag[i]c;elseanss;}else{for(int j(i-1)*s1;ji*s;j){if(a[j]!c)a[j]c;elseans;}tag[i]c;}}return ans;
}
int main(){memset(tag,-1,sizeof(tag));int n;cinn;ssqrt(n);for(int i1;in;i)cina[i];for(int i1;in;i)block[i](i-1)/s1;for(int i1;in;i){int l,r,c;cinlrc;coutquery(l,r,c)endl;}return 0;
}
HDU 5057:
分块板题。
#include bits/stdc.h
using namespace std;
const int maxn100005;
int v[maxn][15],tag[320][15][15],a[maxn];
void update(int x,int y,int z){for(int d1;d10;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 Ll/S,Rr/S,res0;if(LR){for(int il;ir;i)res(v[i][d]p);}else{for(int il;i(L1)*S;i)res(v[i][d]p);for(int iR*S;ir;i)res(v[i][d]p);for(int iL1;iR;i)restag[i][d][p];}return res;
}
int main(){int t;cint;while(t--){memset(tag,0,sizeof(tag));memset(v,0,sizeof(v));int n,m;cinnm;Ssqrt(n);for(int i1;in;i){cina[i];update(i,a[i],1);}while(m--){char op;cinop;if(opS){int x,y;cinxy;update(x,a[x],-1);update(x,y,1);a[x]y;}else{int l,r,d,p;cinlrdp;coutquery(l,r,d,p)endl;}}}return 0;
}
友情提醒:不要Ctrl CCtrl V
