2012长春网赛的题目，光头了...悲剧.
现在知道做了。
分组为[a,b]区间内除k余m的分为一组。这样按组来更新就好了。
这题的突破点就在于k很小。
线段树：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define MN 50010
using namespace std;int tree[MN<<2][55];
int flag[MN<<2];
int b[11][11],num[MN];void build( int l,int r,int rt )
{flag[rt]=0;for( int i=0;i<55;i++ )tree[rt][i]=0;if( l==r )return ;int m=(l+r)>>1;build( l,m,rt<<1 );build( m+1,r,rt<<1|1 );
}void pushDown( int rt )
{if( flag[rt] ){flag[rt<<1|1]=flag[rt<<1]=flag[rt];flag[rt]=false;for( int i=0;i<55;i++ ){tree[rt<<1][i]+=tree[rt][i];tree[rt<<1|1][i]+=tree[rt][i];tree[rt][i]=0;}}
}int query( int pos,int l,int r,int rt )
{if( l==r ){int ret=0;for( int i=1;i<=10;i++ )ret+=tree[rt][b[i][pos%i]];return ret;}pushDown(rt);int m=(l+r)>>1;if( pos<=m )return query( pos,l,m,rt<<1 );elsereturn query( pos,m+1,r,rt<<1|1 );
}void update( int mod,int L,int R,int k,int c,int l,int r,int rt )
{if( L<=l&&r<=R ){tree[rt][b[k][mod]]+=c;flag[rt]=true;return ;}int m=(l+r)>>1;if( L<=m )update( mod,L,R,k,c,l,m,rt<<1 );if( m<R )update( mod,L,R,k,c,m+1,r,rt<<1|1 );
}int main()
{int cnt=0;for( int i=1;i<11;i++ )for( int j=0;j<i;j++ )b[i][j]=cnt++;int N,M;while( scanf("%d",&N)!=EOF ){build(1,N,1);for( int i=1;i<=N;i++ )scanf( "%d",&num[i] );scanf( "%d",&M );getchar();while( M-- ){char str[111];gets(str);int a,b,k,c;if( sscanf( str,"2 %d",&a ) )printf( "%d\n",query(a,1,N,1)+num[a] );else if( sscanf( str,"1 %d %d %d %d",&a,&b,&k,&c) )update( a%k,a,b,k,c,1,N,1 );}}return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MN 55555
using namespace std;int tree[MN][11][11];
int N;void update( int mod,int pos,int k,int c )
{int x=pos;while( x ){tree[x][k][mod]+=c;x-=x&(-x);}
}int query( int a,int x )
{int ret=0;while( x<=N ){for( int i=1;i<=10;i++ )ret+=tree[x][i][a%i];x+=x&(-x);}return ret;
}int main()
{while( scanf("%d",&N)!=EOF ){memset( tree,0,sizeof(tree) );int num[MN];for( int i=1;i<=N;i++ )scanf( "%d",&num[i] );int M;scanf( "%d",&M );getchar();while( M-- ){char str[111];gets(str);int a,b,k,c;if( sscanf(str,"2 %d",&a) )printf( "%d\n",query(a,a)+num[a] );else if( sscanf(str,"1 %d %d %d %d",&a,&b,&k,&c) ){update( a%k,b,k,c );update( a%k,a-1,k,-c );}}}return 0;
}