HDU 4267 A Simple Problem with Integers(12年长春 线段树)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出n个数，每次将一段区间内满足(i-l)%k==0 （r>=i>=l） 的数ai增加c
http://acm.hdu.edu.cn/showproblem.php?pid=4267
比较容易往线段树上想的。但是由于更新的是一些离散的点，比较麻烦
可以考虑这些点的共性，总是隔几个，更新一个，那窝萌把区间内的数关于k的余数分组
这样每次更新的都是其中的一组，而且是连续的。
由于 K比较小，这是本题的突破口，那么关于k的余数情况，最多只有55种。
即如果k=1，则分为1组，k=2分为2组……
一开始傻叉了打算维护55棵线段树，其实也是可以的，更新只需要1棵，查询是10棵，还是可以接受的。
不过只需要在线段树结点维护这55种情况即可。
不过内存比较紧，要把所有的情况压缩一下，不能开10*10的空间。
同样更新只需要一个，最终统计的话，需要遍历所有的K，也就是最多是10.
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<set>#include<vector>#include<string>#include<map>#define eps 1e-7#define LL long long#define N 500005#define zero(a) fabs(a)<eps#define lson step<<1#define rson step<<1|1#define MOD 1234567891#define pb(a) push_back(a)using namespace std;struct Node{ int left,right,add[55],sum; int mid(){return (left+right)/2;}}L[4*N];int a[N],n,b[11][11];void Bulid(int step ,int l,int r){ L[step].left=l; L[step].right=r; L[step].sum=0; memset(L[step].add,0,sizeof(L[step].add)); if(l==r) return ; Bulid(lson,l,L[step].mid()); Bulid(rson,L[step].mid()+1,r);}void push_down(int step){ if(L[step].sum){ L[lson].sum+=L[step].sum; L[rson].sum+=L[step].sum; L[step].sum=0; for(int i=0;i<55;i++){ L[lson].add[i]+=L[step].add[i]; L[rson].add[i]+=L[step].add[i]; L[step].add[i]=0; } }}void update(int step,int l,int r,int num,int i,int j){ if(L[step].left==l&&L[step].right==r){ L[step].sum+=num; L[step].add[b[i][j]]+=num; return; } push_down(step); if(r<=L[step].mid()) update(lson,l,r,num,i,j); else if(l>L[step].mid()) update(rson,l,r,num,i,j); else { update(lson,l,L[step].mid(),num,i,j); update(rson,L[step].mid()+1,r,num,i,j); }}int query(int step,int pos){ if(L[step].left==L[step].right){ int tmp=0; for(int i=1;i<=10;i++) tmp+=L[step].add[b[i][pos%i]]; return a[L[step].left]+tmp; } push_down(step); if(pos<=L[step].mid()) return query(lson,pos); else return query(rson,pos);}int main(){ int cnt=0; for(int i=1;i<=10;i++) for(int j=0;j<i;j++) b[i][j]=cnt++; while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); Bulid(1,1,n); int q,d; scanf("%d",&q); while(q--){ int k,l,r,m; scanf("%d",&k); if(k==2){ scanf("%d",&m); printf("%d\n",query(1,m)); } else{ scanf("%d%d%d%d",&l,&r,&d,&m); update(1,l,r,m,d,l%d); } } } return 0;}