Codeforces 228D Zigzag

用BIT來實作，接下來就是枚舉所有的可能

本以為有更好的解法，但是CF的主機快，不會TLE

而且官方解答也是如此

//By momo
#include<cstdio>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std;

LL n, a[N];
struct BIT{

    LL dat[N];
    void ins(LL x, LL v, LL d){ while(x <= n){ dat[x] += v-d; x += x&-x; } }
    LL qry(LL x){ LL ret = 0; while(x > 0){ ret += dat[x]; x -= x&-x; } return ret; }

}bit[10][11];

int main(){
    
    scanf("%I64d", &n);
    for(LL x = 1; x <= n; x++){
        scanf("%I64d", &a[x]);
        for(LL i = 2; i <= 10; i += 2) bit[i/2+1][x%i].ins(x, a[x], 0);
    }
    
    LL m; scanf("%I64d", &m);
    while(m--){

        LL ty;
        scanf("%I64d", &ty);

        if(ty == 1){
            LL x, v;
            scanf("%I64d%I64d", &x, &v);
            for(LL i = 2; i <= 10; i += 2) bit[i/2+1][x%i].ins(x, v, a[x]);
            a[x] = v;
        }
        else{
            LL l, r, z;
            scanf("%I64d%I64d%I64d", &l, &r, &z);
            LL ans = 0, M = 2*(z-1);
            for(LL i = 1; i <= M; i++){
                LL v = (i == M? 2: ((i <= z)? i: 2 * z - i));
                ans += v * (bit[z][(i+l-1) % M].qry(r) - bit[z][(i+l-1) % M].qry(l-1));
            }
            printf("%I64d\n", ans);
        }

    }
}