HDU 4267 A Simple Problem with Integers --树状数组

题意:给一个序列,操作1:给区间[a,b]中(i-a)%k==0的位置 i 的值都加上val  操作2:查询 i 位置的值

解法:树状数组记录更新值。 由 (i-a)%k == 0 得知 i%k == a%k,又因为k <= 10,想到建55棵树状数组,即对每个(k,x%k)都建一棵树状数组,每次更新时,在第(k,a%k)棵树状数组上更新a这个点,更新值为val,然后再b+1处更新值为-val,即在[a,b]内更新了val。

查询pos的时候,求出每一个树状数组(k,pos%k)的sum值即可。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50007 int c[N][][];
int n,ka[N]; int lowbit(int x){ return x & (-x); }; void modify(int pos,int k,int mod,int val)
{
if(pos == ) return;
while(pos <= n)
{
c[pos][k][mod] += val;
pos += lowbit(pos);
}
} int getsum(int pos)
{
int res = ;
int tmp = pos;
while(pos > )
{
for(int i=;i<=;i++)
res += c[pos][i][tmp%i];
pos -= lowbit(pos);
}
return res;
} int main()
{
int m,a,b,k,val,i,j;
int op;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<=n;i++)
scanf("%d",&ka[i]);
memset(c,,sizeof(c));
scanf("%d",&m);
while(m--)
{
scanf("%d",&op);
if(op == )
{
scanf("%d%d%d%d",&a,&b,&k,&val);
modify(a,k,a%k,val);
modify(b+,k,a%k,-val);
}
else
{
scanf("%d",&a);
printf("%d\n",ka[a] + getsum(a));
}
}
}
return ;
}
上一篇:关于组件的认识


下一篇:树状数组 && 线段树应用 -- 求逆序数