CF228D Zigzag - c++编程基础

题目大意:
要求对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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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 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 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 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 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 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 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;
}