CF228D Zigzag

題目大意:
要求對a[]單點更新和詢問和.

和的形式:

s的定義:

題目思路:
小小抱怨一下,這題到比賽結束時居然才10幾人搞出來,真坑爹= =...
很明顯線段樹直接上,入手處2<=z<=6,結點上保存z=2~6的各個和.
從s的定義知道,1<=s<=z,z最大是6,而且我們還發現,s是一個循環的數列:1,2,3,...,z,z-1,z-2,...,1,所以向上更新即為
sum[rt][z][i]=sum[ls][z][i]+sum[rs][z][(i+左子的長度)%cf[z]],cf[z]表示循環節長度.

代碼:
[cpp]
#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 
#include <ctype.h> 
#include <math.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
//#define ll __int64 
#define ll long long 
#define ls rt<<1 
#define rs ls|1 
#define lson l,mid,ls 
#define rson mid+1,r,rs 
#define middle l+r>>1 
#define esp (1e-8) 
#define type int 
#define clr(x,c) memset(x,c,sizeof(x)) 
#define MOD 1000000007 
typedef pair<int,int> pii; 
 
void swap(int &x,int &y){int t=x;x=y;y=t;} 
type max(type x,type y){return x>y? x:y;} 
type min(type x,type y){return x<y? x:y;} 
const int inf=0x3F3F3F3F; 
//const double pi=acos(-1.0); 
const int M=100000 +5; 
int T,cas; 
 
int n,m; 
ll a,sum[M<<2][5][11],s[5][M]; 
ll cf[5]={2,4,6,8,10}; 
 
void preSof(){ 
    for(ll z=2;z<=6;z++){ 
        ll md=(z-1)<<1; 
        for(ll i=1;i<M;i++){ 
            ll j=i%md; 
            if(!j) s[z-2][i-1]=2; 
            else if(j<=z) s[z-2][i-1]=j; 
            else s[z-2][i-1]=(z<<1)-j; 
        } 
    } 
    return; 
} 
 
void pushUp(int llen,int rt){ 
    for(ll z=2;z<=6;z++) 
        for(ll i=0;i<cf[z-2];i++) 
            sum[rt][z-2][i]=sum[ls][z-2][i]+sum[rs][z-2][(i+llen)%cf[z-2]]; 
} 
 
void build(int l,int r,int rt){ 
    if(l==r){ 
        scanf("%I64d",&a); 
        for(ll z=2;z<=6;z++) 
            for(ll i=0;i<cf[z-2];i++) 
                sum[rt][z-2][i]=a*s[z-2][i]; 
        return; 
    } 
    int mid=middle; 
    build(lson),build(rson); 
    pushUp(mid-l+1,rt); 
} 
 
void update(int l,int r,int rt,int p,ll c){ 
    if(l==r){ 
        for(ll z=2;z<=6;z++) 
            for(ll i=0;i<cf[z-2];i++) 
                sum[rt][z-2][i]=c*s[z-2][i]; 
        return; 
    } 
    int mid=middle; 
    if(p<=mid) update(lson,p,c); 
    else update(rson,p,c); 
    pushUp(mid-l+1,rt); 
} 
 
ll query(int l,int r,int rt,int L,int R,int z,int i){ 
    if(L==l && r==R){ 
        return sum[rt][z][i]; 
    } 
    int mid=middle; 
    if(R<=mid) return query(lson,L,R,z,i); 
    if(mid<L) return query(rson,L,R,z,i); 
    return query(lson,L,mid,z,i)+query(rson,mid+1,R,z,(i+mid-L+1)%cf[z]); 
} 
 
void run(){ 
    int i,j,t,p,v,l,r,z; 
    build(1,n,1); 
    scanf("%d",&m); 
    while(m--){ 
        scanf("%d",&t); 
        if(t==1){ 
            scanf("%d%d",&p,&v); 
            update(1,n,1,p,ll(v)); 
        }else{ 
            scanf("%d%d%d",&l,&r,&z); 
            printf("%I64d\n",query(1,n,1,l,r,z-2,0)); 
        } 
    } 
} 
 
int main(){ 
    //freopen("1.in","r",stdin); 
    //freopen("1.out","w",stdout); 
    preSof(); 
    //run(); 
    while(~scanf("%d",&n)) run(); 
    //for(scanf("%d",&T),cas=1;cas<=T;cas++) run(); 
    return 0; 
}