题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4267
题目大意：给你一列数区间范围为[1，n]，区间每个数有一个对应值a[i]。接下来有Q个操作
操作1： "1 a b k c"， 区间[a，b]内满足条件（i-a）%k==0的数值a[i]加c。
操作2：“2 a” ，输出a[i]的值。
解题思路：这题蛋都碎成渣渣了，RE几次，MLE无数次。
1、按线段树建树情况可推出，即使成为完全平衡树开也只有2*n-1个节点，开2*n的大小完全没问题啊，但它就是RE，不解。
2、这题我的初始化开始没有建build（）函数，而是直接对flag[][]初始化，这里MLE无数次，建树开build（）函数成段成段初始化就过了，蛋都碎成渣渣了。
说说解题思路吧，重点在（i-a）%k==0，这样的i是断开的，无法成段操作，傻×才去暴力。注意到k比较小，枚举k以及余数的组合，k=1有1种，k=2有2种，……k=10有10种，所以总共有（1+2+3....+10=55种组合），我们将每种组合压缩成一个状态。
建树操作： 成段初始化，不然MLE。
更新操作： 当查询到对应区间[tl，tr]，对应的组合状态flag[u][mo]加上c，返回。
查询操作：对x路过的区间进行操作，当x与k（1<=k<=10）对应的余数值这个状态有值时，加上这个值。
View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 7 #define lz 2*u,l,mid 8 #define rz 2*u+1,mid+1,r 9 const int maxn=500005; 10 int flag[4*maxn][55], val[maxn]; 11 12 void build(int u, int l, int r) ///开始没这样建树初始化，而是直接memset(flag,0,sizeof(flag))，一直MLE，蛋都碎成渣渣了 13 { 14 memset(flag[u],0,sizeof(flag[u])); 15 if(l==r) return ; 16 int mid=(l+r)>>1; 17 build(lz); 18 build(rz); 19 } 20 21 void Update(int u, int l, int r, int tl, int tr, int mo, int k, int c) 22 { 23 if(tl<=l&&r<=tr) 24 { 25 for(int i=1; i<k; i++) mo+=i; 26 flag[u][mo]+=c; 27 return ; 28 } 29 int mid=(l+r)>>1; 30 if(tr<=mid) Update(lz,tl,tr,mo,k,c); 31 else if(tl>mid) Update(rz,tl,tr,mo,k,c); 32 else 33 { 34 Update(lz,tl,mid,mo,k,c); 35 Update(rz,mid+1,tr,mo,k,c); 36 } 37 } 38 39 void Query(int u, int l, int r, int x, int &res) 40 { 41 for(int i=1; i<=10; i++) 42 { 43 int mo=x%i; 44 for(int j=1; j<i; j++) mo+=j; 45 res+=flag[u][mo]; 46 } 47 if(l==r) return ; 48 int mid=(l+r)>>1; 49 if(x<=mid) Query(lz,x,res); 50 else Query(rz,x,res); 51 } 52 53 int main() 54 { 55 int n, Q; 56 while(~scanf("%d",&n)) 57 { 58 for(int i=1; i<=n; i++) scanf("%d",val+i); 59 int op, a, b, k, c; 60 build(1,1,n); 61 scanf("%d",&Q); 62 while(Q--) 63 { 64 scanf("%d",&op); 65 if(op==1) 66 { 67 scanf("%d%d%d%d",&a,&b,&k,&c); 68 Update(1,1,n,a,b,a%k,k,c); 69 } 70 else 71 { 72 scanf("%d",&a); 73 int res=0; 74 Query(1,1,n,a,res); 75 printf("%d\n",res+val[a]); 76 } 77 } 78 } 79 return 0; 80 }