弹药分配 （HGOI 2019.2.17 T2）

## 题目大意 给出一个数列$a_1…a_n$,有两个操作：1.给出一个区间[a,b]，给这个区间内所有编号(i-a)%k=0的数加上c； 2.询问编号为x的值 ## 数据范围 n,m<=50000,1<=k<=10,ans<=maxlongint ### 解法 显然，直接暴力极限数据是会T的，但是这次好像数据很水，被一部分人水过去了 这道题，显然有间隔地只能一个一个修改，我们不能用线段树或者树状数组来处理。但是如果把它们放到一起就能处理了 用一个三维数组p[i][j][k]存间隔为i，除i余数为j，的第k个被加了多少。然后操作的时候集中用树状数组区间加 在询问的时候，树状数组单点询问，但记得要把所有的间隔枚举一遍都加起来 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define lowbit(x) x&(-x) using namespace std; int n,m; int a[50100]; int p[20][20][50100]; void Add(int b,int c,int x,int y) { while(x<=n) { p[b][c][x]+=y; x+=lowbit(x); } } int sum(int b,int c,int x) { int res=0; while(x>0) { res+=p[b][c][x]; x-=lowbit(x); } return res; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); while(m--) { int tmp,x,y,k,c; scanf("%d",&tmp); if(tmp==1) { scanf("%d%d%d%d",&x,&y,&k,&c); Add(k,x%k,x/k+1,c); Add(k,x%k,(y-x%k)/k+2,-c);//树状数组用差分实现区间加 } else { scanf("%d",&x); int res=0; for(int i=1;i<=10;i++) res+=sum(i,x%i,x/i+1);//所有间隔枚举相加 printf("%d\n",a[x]+res); } } return 0; } ```