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++ ,
