这道题即区间更新,单点查询,所以只需要维护区间的增加量即可。
因为1<=k<=10,所以对于不同的起始区间不同的k,一共有55种情况,所以,用开个55的数组即可维护。
利用ZKW线段树思想,标记永久化,每次查到根就over。。
这题方法很多的说,维护10棵树状数组也行,sqrt(n)的方法也行。。。
不过比赛时没想到怎么解决不同的起始区间的k值,算了下还可能MLE,没敢写。。。郁闷。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
using namespace std;
int n, q, num;
int add[1<<17][55];
int left[1<<17], right[1<<17];
int arr[50100];
void init()
{
memset(add,0,sizeof(add));
for ( int i = 0 ; i < num ; i++ )
left[i+num]=right[i+num]=i;
for ( int i = num-1 ; i ; i-- )
{
left[i]=left[L(i)];
right[i]=right[R(i)];
}
}
void update(int s, int t, int k, int val)
{
int tag = s%k;
for ( int i = 1 ; i < k ; i++ )
tag+=i;
for ( s=s+num-1, t=t+num+1 ; s^t^1 ; s>>=1, t>>=1 )
{
if (~s&1)
add[s^1][tag]+=val;
if (t&1)
add[t^1][tag]+=val;
}
}
int query(int m)
{
int ans=0, start=m;
for ( m+=num ; m ; m>>=1 )
for ( int k = 1 ; k <= 10 ; k++ )
{
int tag=start%k;
for ( int i = 1 ; i < k ; i++ )
tag+=i;
ans+=add[m][tag];
}
return ans;
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while (EOF!=scanf("%d", &n))
{
for ( int i = 1; i <= n ; i++ )
scanf("%d", arr+i);
scanf("%d", &q);
int cmd, l,r,k,val;
for (num=1;num<(n+2);num<<=1);
init();
while (q--)
{
scanf("%d", &cmd);
if (1==cmd)
{
scanf("%d%d%d%d", &l, &r, &k, &val);
update(l,r,k,val);
}
else if (2==cmd)
{
scanf("%d", &k);
printf("%d\n", arr[k]+query(k));
}
}
}
return 0;
}