hdu4267--A Simple Problem with Integers（树状数组）

题目链接：点击打开链接

题目大意：有一个n个数的序列，有两种操作1 a b k c 在区间[a,b]内的i，如果满足(i-a)%k == 0 那么第i个数就加上c，

2 a问第a个数的值是什么，首先给出n个数的初始值，然后是q次操作，完成每次操作，如果是询问的话，输出那个值。

第一次考虑用线段树，如果一次操作1 a b k c中[a,b]能覆盖当前线段树的一个小段[l,r]的话，那么对于这个小段中的i，

如果满足(i-a)%k == 0 ，那么第i个数的值就会加c，我们将式子变形一下( (i-l)+(l-a) )%k == 0，这个对于一个给定的i来说，(i-l)的值是确定的，那么只需要枚举k(1～10)就可以计算出会有多少个操作对第i个数存在影响，而且对于不同操作来说如果k和(l-a)%k的值都是相同的，那么他们作用的i也就是相同的，就可以合并。cl[ rt ][ k ][ (l-a)%k ]，线段树这样建立，对于每次询问就可以log(n)的时间查询对第i个数的修改情况，在加上初始值，就是最终的结果。

但是这样做一直MLE，所以将它转化成树状数组，把一次修改拆成两部分:

1 a b k c拆成 1 a n k c和1 (b-a)/k*k+a+k n k -c，其中(r-l)/k*k+l+k是从a开始不断累加k中第一个超过b的数，这样就可以保证原来的操作是不变的。

转化成装数组之后，就把原本的每段的l转化成了累加的时候的节点的位置，按照同样的方法储存数据，求每个数在它之前存在的所有操作对它的影响，这样计算出最终结果。

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <cmath>
#include <map>
#include <stack>
#include <algorithm>
using namespace std ;
#pragma comment(linker, "/STACK:102400000,102400000")
#define LL __int64
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define root 1,n,1
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define int_rt int l,int r,int rt
const int mod=1e9+7;
const int MAXN = 50000+10 ;
int cl[MAXN][11][11] , a[MAXN] ;
int n , q ;
int lowbit(int x) {
    return x & -x ;
}
void add(int a,int k,int c) {
    int i = a , temp ;
    while( i <= n ) {
        temp = (i-a)%k ;
        if( temp == 0 ) temp = k ;
        cl[i][k][temp] += c ;
        i += lowbit(i) ;
    }
}
int sum(int a) {
    int i = a , j , temp , ans = 0 ;
    while( i ) {
        for(j = 1 ; j < 11 ; j++)
            ans += cl[i][j][ j-(a-i)%j ] ;
        i -= lowbit(i) ;
    }
    return ans ;
}
int main() {
    int i , j , k , l , r , c ;
    while( scanf("%d", &n) != EOF ) {
        for(i = 1 ; i <= n ; i++)
            scanf("%d", &a[i]) ;
        memset(cl,0,sizeof(cl)) ;
        scanf("%d", &q) ;
        while( q-- ) {
            scanf("%d", &i) ;
            if( i == 1 ) {
                scanf("%d %d %d %d", &l, &r, &k, &c) ;
                add(l,k,c) ;

                add((r-l)/k*k+l+k,k,-c) ;
            }
            else {
                scanf("%d", &i) ;
                printf("%d\n", sum(i)+a[i]) ;
            }
        }
    }
    return 0 ;
}

hdu4267--A Simple Problem with Integers（树状数组）

原文：http://blog.csdn.net/winddreams/article/details/47998019