CF 228D Zigzag(线段树)


		大概又是这样的题，(2<=z<=6)然后显然又是多棵线段树，对于不同的z，分别维护。
但是每次可以看到下标应该为i-l+1，所以不是固定的。
但是s[i][j]中j是和i的模是有关，那么就对于不同的z，再维护多棵线段树，对于每一种模的情况都统计一下。
大概线段树维护的就是一个区间第一个的位置是%i==j是的和
大概在push_up以及查询的时候是和HDU 4288类似的。
[cpp] 
#include<iostream>   
#include<cstdio>   
#include<cstring>   
#define mem(a,b) memset(a,b,sizeof(a))   
#define N 100005   
#define lson step<<1   
#define rson step<<1|1   
#define LL long long    
using namespace std;  
struct Seg_tree{  
    int left,right;  
    LL sum[7][10];  
}L[N<<2];  
int s[7][10];  
int n,m,a[N];  
void Init(){  
    for(int i=2;i<=6;i++){  
        for(int j=0;j<2*(i-1);j++)  
            if(j==0) s[i][j]=2;  
            else if(j<=i) s[i][j]=j;  
            else if(j>i) s[i][j]=2*i-j;  
    }  
}  
void push_up(int step){  
    for(int i=2;i<=6;i++)  
        for(int j=0;j<2*(i-1);j++){  
            int d=L[lson].right-L[lson].left+1;  
            L[step].sum[i][j]=(L[lson].sum[i][j]+L[rson].sum[i][(j+d)%(2*(i-1))]);  
        }  
}  
void bulid(int step,int l,int r){  
    L[step].left=l;  
    L[step].right=r;  
    if(l==r){  
        for(int i=2;i<=6;i++)  
            for(int j=0;j<2*(i-1);j++)  
                L[step].sum[i][j]=(LL)s[i][j]*a[l];  
        return ;  
    }  
    int m=(l+r)>>1;  
    bulid(lson,l,m);  
    bulid(rson,m+1,r);  
    push_up(step);  
}  
LL query(int step,int l,int r,int z,int x){  
    if(L[step].left==l&&L[step].right==r){  
        // mod z == x   
        return L[step].sum[z][x];  
    }  
    int m=(L[step].left+L[step].right)>>1;  
    if(r<=m) return query(lson,l,r,z,x);  
    else if(l>m) return query(rson,l,r,z,x);  
    else return query(lson,l,m,z,x)+query(rson,m+1,r,z,(x+(m-l+1))%(2*(z-1)));  
}  
void update(int step,int pos,int val){  
    if(L[step].left==pos&&L[step].right==pos){  
        // mod (2*(i-1)) == j   
        for(int i=2;i<=6;i++)  
            for(int j=0;j<2*(i-1);j++)  
                L[step].sum[i][j]=(LL)val*s[i][j];  
        return ;  
    }  
    int m=(L[step].left+L[step].right)>>1;  
    if(pos<=m) update(lson,pos,val);  
    else update(rson,pos,val);  
    push_up(step);  
}  
int main(){  
    Init();  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
        scanf("%d",&a[i]);  
    bulid(1,1,n);  
    scanf("%d",&m);  
    while(m--){  
        int k,l,r,z;  
        scanf("%d",&k);  
        if(k==1){  
            scanf("%d%d",&l,&z);  
            update(1,l,z);  
        }  
        else{  
            scanf("%d%d%d",&l,&r,&z);  
            printf("%I64d\n",query(1,l,r,z,1));  
        }  
    }  
    return 0;  
}  
 
#include<iostream>
#include<cstdio>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define N 100005
#define lson step<<1
#define rson step<<1|1
#define LL long long 
using namespace std;
struct Seg_tree{
    int left,right;
    LL sum[7][10];
}L[N<<2];
int s[7][10];
int n,m,a[N];
void Init(){
    for(int i=2;i<=6;i++){
        for(int j=0;j<2*(i-1);j++)
            if(j==0) s[i][j]=2;
            else if(j<=i) s[i][j]=j;
            else if(j>i) s[i][j]=2*i-j;
    }
}
void push_up(int step){
    for(int i=2;i<=6;i++)
        for(int j=0;j<2*(i-1);j++){
            int d=L[lson].right-L[lson].left+1;
            L[step].sum[i][j]=(L[lson].sum[i][j]+L[rson].sum[i][(j+d)%(2*(i-1))]);
        }
}
void bulid(int step,int l,int r){
    L[step].left=l;
    L[step].right=r;
    if(l==r){
        for(int i=2;i<=6;i++)
            for(int j=0;j<2*(i-1);j++)
                L[step].sum[i][j]=(LL)s[i][j]*a[l];
        return ;
    }
    int m=(l+r)>>1;
    bulid(lson,l,m);
    bulid(rson,m+1,r);
    push_up(step);
}
LL query(int step,int l,int r,int z,int x){
    if(L[step].left==l&&L[step].right==r){
        // mod z == x
        return L[step].sum[z][x];
    }
    int m=(L[step].left+L[step].right)>>1;
    if(r<=m) return query(lson,l,r,z,x);

补充：软件开发 , C++ ,