Time Limit: 5000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Description Let A1, A2, ... , AN be N elements. You need to deal with two kinds of operations. One type of operation is to add a given number to a few numbers in a given interval. The other is to query the value of some element.Input There are a lot of test cases. The first line contains an integer N. (1 <= N <= 50000) The second line contains N numbers which are the initial values of A1, A2, ... , AN. (-10,000,000 <= the initial value of Ai <= 10,000,000) The third line contains an integer Q. (1 <= Q <= 50000) Each of the following Q lines represents an operation. "1 a b k c" means adding c to each of Ai which satisfies a <= i <= b and (i - a) % k == 0. (1 <= a <= b <= N, 1 <= k <= 10, -1,000 <= c <= 1,000) "2 a" means querying the value of Aa. (1 <= a <= N)
Output For each test case, output several lines to answer all query operations.
Sample Input 4 1 1 1 1 14 2 1 2 2 2 3 2 4 1 2 3 1 2 2 1 2 2 2 3 2 4 1 1 4 2 1 2 1 2 2 2 3 2 4 Sample Output 1 1 1 1 1 3 3 1 2 3 4 1 题意：给你一个序列，有两个操作，1是将区间[a,b]内满足 (i - a) % k == 0的位置加上c，2是查询a位置的数。 分析：因为k比较小，所以可以对于每一个k建立一个树状数组，这样还不够，无法确定应该向哪个位置加数，再加一维表示模k的余数，这样建立就行了。 对于更新，我们只需要对F[k][a%k][x]的树状数组更新，因为是区间更新，可以考虑加一段和剪一段，在a这个位置更新c，在b+1的位置减去c就不影响后面了。 查询就普通查询，注意要加上初始值。 #include<stdio.h> #include<string.h> #include<iostream> using namespace std; const int MAXN = 50000+100; int F[12][12][MAXN]; int num[MAXN]; int n; void update(int s,int t,int x,int val) { while(x<=n) { F[s][t][x]+=val; x+=x&-x; } } int query(int s,int t,int x) { int res=0; while(x>0) { res+=F[s][t][x]; x-=x&-x; } return res; } int main() { int m; int op,a,b,k,c; while(scanf("%d",&n)!=EOF) { memset(F,0,sizeof(F)); for(int i=1;i<=n;i++) scanf("%d",&num[i]); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d",&op); if(op==1) { scanf("%d%d%d%d",&a,&b,&k,&c); int t=a%k; update(k,t,a,c); update(k,t,b+1,-c); } else if(op==2) { int ans=0; scanf("%d",&a); for(int j=1;j<=10;j++) ans+=query(j,a%j,a); printf("%d\n",ans+num[a]); } } } return 0; }
转载于:https://www.cnblogs.com/wangdongkai/p/5747122.html
