A Simple Problem with Integers（100棵树状数组）

A Simple Problem with Integers

Time Limit: 5000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5034 Accepted Submission(s): 1589

Problem 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

题解：树状数组，每次更新(i - a)%k = 0 的位置的值，每次询问a位置的值；所以i%k = a%k;

开100棵树状数组，tree[x][k][mod];

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

const int MAXN = ;

int tree[MAXN][][];

int num[MAXN];

int lowbit(int x){return x & (-x);}

void add(int x, int k, int mod, int v){

    while(x < MAXN){

        tree[x][k][mod] += v;

        x += lowbit(x);

    }

}

int sum(int x, int a){

    int ans = ;

    while(x > ){

        for(int i = ; i <= ; i++){

            ans += tree[x][i][a % i];

        }

        x -= lowbit(x);

    }

    return ans;

}

int main(){

    int N, M;

    while(~scanf("%d", &N)){

        memset(tree, , sizeof(tree));

        for(int i = ; i <= N; i++){

            scanf("%d", &num[i]);

        }

        scanf("%d", &M);

        int q, a, b, k, c;

        while(M--){

            scanf("%d%d", &q, &a);

            if(q == ){

                scanf("%d%d%d", &b, &k, &c);

                add(a, k, a % k, c);

                add(b + , k, a % k, -c);

            }

            else{

                printf("%d\n", num[a] + sum(a, a));

            }

        }

    }

    return ;

}