2016年建设网站赚钱吗,免费wordpress资源,网站建设与网页设计课程设计,如何制作一个小程序插讲一下分块 题目#xff1a;#xff08;POJ 3648#xff09; 一个简单的整数问题 前缀和往往用于静态的不会修改的区间和。遇到经常修改的区间问题#xff0c;就要用分块或线段树来维护了。 分块算法是优化后的暴力#xff0c;分块算法有时可以维护一些线段树维护不了的…插讲一下分块 题目POJ 3648 一个简单的整数问题 前缀和往往用于静态的不会修改的区间和。遇到经常修改的区间问题就要用分块或线段树来维护了。 分块算法是优化后的暴力分块算法有时可以维护一些线段树维护不了的东西虽然效率一般不如线段树但是比线段树更易上手。 分块算法分3步骤 1预处理块处理块长往往是根号n每块的左右下标L[], R[]每块的区间和suf[]每个元素所属的块号pos[] 2区间修改对于完整的块仅修改懒标记不完整的就暴力修改a[]和suf[] 3区间查询 对于完整的块直接利用懒和suf不完整的就暴力 #include bits/stdc.h//POJ3648
using namespace std;
const int N100010;
typedef long long ll;
ll a[N],suf[N],add[N];
int L[N],R[N],pos[N];
int n,m,t,l,r,d;
char op[3];
//分块预处理我们处理下标都是从1开始
void build(){//处理t块长L[]R[]每块的左右下标pos[]每个下标的所属块号suf[]每块的和tsqrt(n*1.0);int numn/t;if(n%t) num;for(int i1;inum;i){L[i](i-1)*t1;R[i]i*t;}R[num]n;//更改最后一块的右下标for(int i1;inum;i){for(int jL[i];jR[i];j){pos[j]i;suf[i]a[j];}}
}
//区间修改
void change (int l,int r,ll d){//修改add[]懒标a[]和suf[]int ppos[l],qpos[r];if(pq){//如果在同一块就暴力修改a[]和suf[]for(int il;ir;i) a[i]d;suf[p]d*(r-l1);}else{//完整的块仅修改懒标不完整就暴力for(int ip1;iq-1;i) add[i]d;for(int il;iR[p];i) a[i]d;suf[p]d*(R[p]-l1);for(int iL[q];ir;i) a[i]d;suf[q]d*(r-L[q]1);}
}ll query(int l,int r){int ppos[l],qpos[r];ll ans0;if(pq){//同一块就暴力for(int il;ir;i) ansa[i];ansadd[p]*(r-l1);}else{//完整就sufadd不完整就暴力for(int ip1;iq-1;i) anssuf[i]add[i]*(R[i]-L[i]1);for(int il;iR[p];i) ansa[i];for(int iL[q];ir;i) ansa[i];ansadd[q]*(r-L[q]1);}return ans;
}
int main(){cinnm;for(int i1;in;i){scanf(%lld,a[i]);}build();for(int i1;im;i){scanf(%s %d %d,op,l,r);if(op[0]C){scanf(%d,d);change(l,r,d);}else{printf(%lld\n,query(l,r));}}
}
