BZOJ 3155 Preprefix sum
2017.09.22
题目大意
给你一个数列A，它的前缀和S,让你维护它，支持：修改$A_i$，查询$\sum\limits_{j=1}^{i} S_j. $
线段树维护S，对于每一次修改修改$i$以后的所有$S_i$，对于询问直接求和就好了= =
注意因为这题线段树节点值是long long的，所以中间节点也要有1ll加成。在计算值的时候我用的int然后就爆了……
（AC代码后纯口胡= =
#include <cstdio>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
int n,m,inx,iny;
long long v[400010],lz[400010],a[100010],s[100010];
char mode[10];
void build(int pos,int l,int r)
{
if(l==r)
{
v[pos]=a[l];
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
v[pos]=v[lson]+v[rson];
}
void pushdown(int pos,int l,int r)
{
if(lz[pos])
{
int mid=(l+r)>>1;
lz[lson]+=lz[pos],lz[rson]+=lz[pos];
v[lson]+=lz[pos]*(mid-l+1),v[rson]+=lz[pos]*(r-mid);
lz[pos]=0;
}
}
void update(int pos,int l,int r,int x,int y,int t)
{
if(x<=l&&r<=y) {v[pos]+=1ll*t*(r-l+1),lz[pos]+=t;return;}
pushdown(pos,l,r);
int mid=(l+r)>>1;
if(x<=mid) update(lson,l,mid,x,y,t);
if(y>mid) update(rson,mid+1,r,x,y,t);
v[pos]=v[lson]+v[rson];
return;
}
long long query(int pos,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return v[pos];
pushdown(pos,l,r);
int mid=(l+r)>>1;
long long ret=0;
if(x<=mid) ret+=query(lson,l,mid,x,y);
if(y>mid) ret+=query(rson,mid+1,r,x,y);
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",a+i),s[i]=a[i],a[i]+=a[i-1];
build(1,1,n);
while(m--)
{
scanf("%s",mode);
switch(mode[0])
{
case 'Q': scanf("%d",&inx),printf("%lld\n",query(1,1,n,1,inx));break;
case 'M': scanf("%d%d",&inx,&iny),update(1,1,n,inx,n,iny-s[inx]),s[inx]=iny;break;
}
}
return 0;
}
F**k!
md我看错题了，原来以为是区间修改，更改一个值之后产生一个等差序列的东西，好不容易写完发现咋调都不对 后来发现单点修改$A_i$对于$S_i$增长是恒定值，对于$SS_i$来讲虽然是等差数列但是我tm要维护的不是这个啊，这是SB线段树啊我c
//WA Code
#include <cstdio>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
#define N 100010
int n,m,inx,iny;
long long a[N],s[N],v[N<<2],lz[N<<2],up[N<<2];
char mode[10];
void pushup(int pos) {v[pos]=v[lson]+v[rson];}
void pushdown(int pos,int l,int r)
{
if(up[pos])
{
int mid=(l+r)>>1;
v[lson]+=(lz[pos]*(mid-l+1)+(mid-l+1)*(mid-l)/2*up[pos]),v[rson]+=(lz[pos]*(r-mid)+(r-mid)*(r-mid-1)/2*up[pos]);
lz[lson]+=lz[pos],lz[rson]+=lz[pos];
up[lson]+=up[pos],up[rson]+=up[pos];
lz[pos]=up[pos]=0;
}
}
void build(int pos,int l,int r)
{
if(l==r)
{
v[pos]=a[l];
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(pos);
}
void update(int pos,int l,int r,int x,int y,int a,int b)
{
if(x<=l&&r<=y)
{
v[pos]+=(a*(r-l+1)+(r-l+1)*(r-l)/2*b),lz[pos]+=a,up[pos]+=b;
return;
}
pushdown(pos,l,r);
int mid=(l+r)>>1;
if(x<=mid) update(lson,l,mid,x,y,a,b),a=a+b*(mid-x+1),x=mid+1;
update(rson,mid+1,r,x,y,a,b);
pushup(pos);
}
long long query(int pos,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return v[pos];
pushdown(pos,l,r);
int mid=(l+r)>>1;
long long ret=0;
if(x<=mid) ret+=query(lson,l,mid,x,y);
if(y>mid) ret+=query(rson,mid+1,r,x,y);
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",a+i),s[i]=a[i],a[i]+=a[i-1];
build(1,1,n);
while(m--)
{
scanf("%s",mode);
switch(mode[0])
{
case 'Q': scanf("%d",&inx),printf("%lld\n",query(1,1,n,1,inx));break;
case 'M': scanf("%d%d",&inx,&iny),update(1,1,n,inx,n,iny-s[inx],iny-s[inx]),s[inx]=iny;break;
}
}
return 0;
}