服装设计最好的出路,企业网站优化哪家好,十大互联网公司排名,襄阳seo研究中心分块
分块的思想和珂朵莉树很类似#xff0c;就是把原序列分成若干个块#xff0c;对块进行操作的奇妙思想。复杂度通常带根号。分块的块长也有讲究#xff0c;通常对于大小为 n n n 的数组#xff0c;取距离 n \sqrt n n 最近的 2 2 2 的幂数或直接取 n \sqrt n n…分块
分块的思想和珂朵莉树很类似就是把原序列分成若干个块对块进行操作的奇妙思想。复杂度通常带根号。分块的块长也有讲究通常对于大小为 n n n 的数组取距离 n \sqrt n n 最近的 2 2 2 的幂数或直接取 n \sqrt n n 即可如果 TLE 了可以考虑把块长乘 2 2 2 或除以 2 2 2。
数列分块
最简单的分块。基本上分两步走对于一个操作的区间 [ l , r ] [l,r] [l,r]如果刚好在某个块区间内直接暴力修改 [ l , r ] [l,r] [l,r] 的值如果横跨多个区间先处理整块然后处理边角料。
常用操作如下 区间加法、单点查询 最简单的数列分块操作具体详见代码 #include bits/stdc.h
using namespace std;
#define int long longconst int maxn5e45;
int n,opt,ll,rr,cc,len,a[maxn],id[maxn],tag[maxn];void add(int l,int r,int c)
{int sidid[l],eidid[r];if(sideid)for(int il;ir;i)a[i]c;else{for(int il;id[i]sid;i) a[i]c;for(int isid1;ieid;i) tag[i]c;for(int ir;id[i]eid;i--) a[i]c;}
}signed main()
{cinn;lensqrt(n);for(int i1;in;i) cina[i],id[i](i-1)/len1;for(int i1;in;i){cinoptllrrcc;if(!opt) add(ll,rr,cc);else couta[rr]tag[id[rr]]endl;}return 0;
}区间加法、区间求和 块长同样是 n \sqrt n n 由均值不等式可知此时单词操作的时间复杂度最优为 O ( n ) O(\sqrt n) O(n )。预处理每一个块的区间和 s s s。 对于区间 [ l , r ] [l,r] [l,r] 的查询操作考虑几种情况 若 l l l 和 r r r 在同一个块内暴力统计最坏时间复杂度为 O ( n ) O(\sqrt n) O(n )若 l l l 和 r r r 不在同一个块内暴力统计不完整的块直接累加完整的块的区间和最坏时间复杂度为 O ( n ) O(\sqrt n) O(n )。 对于区间 [ l , r ] [l,r] [l,r] 的加法操作同样按照上面的思考方式 若 l l l 和 r r r 在同一个块内暴力修改区间即可最坏时间复杂度为 O ( n ) O(\sqrt n) O(n )若 l l l 和 r r r 不在同一个块内暴力修改不完整的块同时更新 s s s直接修改完整块的 s s s最坏时间复杂度为 O ( n ) O(\sqrt n) O(n )。 代码如下 #include bits/stdc.h
using namespace std;
#define int long longconst int maxn50005;
int a[maxn],id[maxn],tag[maxn]/*区间直接打标记*/,c,s[maxn],len;void add(int l,int r,int v)
{int sidid[l],eidid[r];//start-id,end-idif(sideid) for(int il;ir;i) a[i]v,s[sid]v;else{for(int il;id[i]sid;i) a[i]v,s[sid]v;for(int ir;id[i]eid;i--) a[i]v,s[eid]v;for(int isid1;ieid;i) tag[i]v,s[i]len*v;}
}int query(int l,int r,int mod)
{int sidid[l],eidid[r],ans0;if(sideid) {for(int il;ir;i) ans(ansa[i]tag[sid])%mod;return ans;}else{for(int il;id[i]sid;i) ans(ansa[i]tag[sid])%mod;for(int ir;id[i]eid;i--) ans(ansa[i]tag[eid])%mod;for(int isid1;ieid;i) ans(anss[i])%mod;return ans;}
}signed main()
{int n;cinn;lensqrt(n);for(int i1;in;i) cina[i],id[i](i-1)/len1,s[id[i]]a[i];while(n--){int opt,l,r;cinoptlrc;if(!opt) add(l,r,c);else coutquery(l,r,c1)endl;}return 0;
}块状数组
