P6215题解

· · 题解

背景

我最爱线段树了。

题目解读

原题传送门

首先我们发现 p^i 珂以进行预处理。

之后，我们发现维护前缀和的前缀和实在有些麻烦。那么我们干脆维护每一个 g(i)。

到目前为止，我们的问题转化成了区间修改，单点修改，区间求和。

因为 k \leq 3，所以我们直接用线段树维护 \sum\limits_{i=l}^{r}g(i)^k \cdot b_i。这坨玩意怎么维护？

操作 1 x y

标记下传和修改一，对于 [l,r] 我们把 g(i) 都加上 v，分别有：

\begin{aligned} \sum\limits_{i=l}^{r}(g_i+v) b_i =\sum\limits_{i=l}^{r}g_ib_i+v \sum\limits_{i=l}^{r}b_i\end{aligned} \begin{aligned} \sum\limits_{i=l}^{r}(g_i+v)^2 b_i &=\sum_{i=l}^{r}(g_i^2+2g_iv+v^2)b_i \\&= \sum\limits_{i=l}^{r}g_i^2b_i+2v \sum\limits_{i=l}^{r}g_ib_i+v^2\sum_{i=l}^{r}b_i \end{aligned} \begin{aligned} \sum\limits_{i=l}^{r}(g_i+v)^3 b_i &=\sum_{i=l}^{r}(g_i^3+3g_i^2v+3g_iv^2+v^3)b_i \\&= \sum\limits_{i=l}^{r}g_i^3b_i+3v \sum\limits_{i=l}^{r}g_i^2b_i+3v^2\sum_{i=l}^{r}g_ib_i+v^3\sum_{i=l}^{r}b_i \end{aligned}

关于维护区间幂次和，可以说是这一题的升级版。

操作 2 x y

直接单点修改即可，操作就是乘以 b_i 的逆元和 y。逆元用费马小定理即可。同时也要把 b_i 赋值为 y。

好了，修改套个模板没什么可讲的，记住能取模的地方一定取模，废话说完了。上代码！

AC_Code

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
typedef long long ak;
const int N=2e5+5;
const ak P=1e9+7;
int n,m,K;
ak p,a[N],b[N],pi[N],g[N];
struct segement{
    ak sumG[4],add;
}xds[N<<2];
ak fastpow(ak u,ak v){
    ak res=1;
    while(v){
        if(v&1) res=res*u%P;
        u=u*u%P;
        v>>=1;
    }
    return res;
}
ak inverse(ak a){
    return fastpow(a,P-2)%P;
}
void pushup(int k){
    xds[k].sumG[0]=(xds[ls].sumG[0]+xds[rs].sumG[0])%P;
    xds[k].sumG[1]=(xds[ls].sumG[1]+xds[rs].sumG[1])%P;
    xds[k].sumG[2]=(xds[ls].sumG[2]+xds[rs].sumG[2])%P;
    xds[k].sumG[3]=(xds[ls].sumG[3]+xds[rs].sumG[3])%P;
}
void build(int l,int r,int k){
    if(l==r){
        xds[k].sumG[0]=b[l]%P;
        xds[k].sumG[1]=g[l]*b[l]%P;
        xds[k].sumG[2]=g[l]*g[l]%P*b[l]%P;
        xds[k].sumG[3]=g[l]*g[l]%P*g[l]%P*b[l]%P;
        return;
    }
    build(l,mid,ls);build(mid+1,r,rs);
    pushup(k);
}
void pushdown(int k){
    if(xds[k].add==0) return;
    xds[ls].add=(xds[ls].add+xds[k].add)%P;
    xds[rs].add=(xds[rs].add+xds[k].add)%P;
    ak pow1=xds[k].add,pow2=pow1*pow1%P,pow3=pow2*pow1%P;
    xds[ls].sumG[3]=(xds[ls].sumG[3]+3*pow1*xds[ls].sumG[2]%P+3*pow2*xds[ls].sumG[1]%P+pow3*xds[ls].sumG[0]%P)%P;
    xds[rs].sumG[3]=(xds[rs].sumG[3]+3*pow1*xds[rs].sumG[2]%P+3*pow2*xds[rs].sumG[1]%P+pow3*xds[rs].sumG[0]%P)%P;
    xds[ls].sumG[2]=(xds[ls].sumG[2]+2*pow1*xds[ls].sumG[1]%P+pow2*xds[ls].sumG[0]%P)%P;
    xds[rs].sumG[2]=(xds[rs].sumG[2]+2*pow1*xds[rs].sumG[1]%P+pow2*xds[rs].sumG[0]%P)%P;
    xds[ls].sumG[1]=(xds[ls].sumG[1]+pow1*xds[ls].sumG[0])%P;
    xds[rs].sumG[1]=(xds[rs].sumG[1]+pow1*xds[rs].sumG[0])%P;
    xds[k].add=0;
}
void ModifyA(int l,int r,int k,int ll,int rr,ak v){
    if(l>=ll&&r<=rr){
        xds[k].sumG[3]=(xds[k].sumG[3]+3*v*xds[k].sumG[2]%P+3*v*v%P*xds[k].sumG[1]%P+v*v%P*v%P*xds[k].sumG[0]%P)%P;
        xds[k].sumG[2]=(xds[k].sumG[2]+2*v*xds[k].sumG[1]%P+v*v%P*xds[k].sumG[0]%P)%P;
        xds[k].sumG[1]=(xds[k].sumG[1]+v*xds[k].sumG[0]%P)%P;
        xds[k].add=(xds[k].add+v)%P;
        return;
    }
    pushdown(k);
    if(ll<=mid) ModifyA(l,mid,ls,ll,rr,v);
    if(rr>mid) ModifyA(mid+1,r,rs,ll,rr,v);
    pushup(k);
}
void ModifyB(int l,int r,int k,int z,ak v){
    if(l==r){
        xds[k].sumG[0]=v;
        xds[k].sumG[1]=xds[k].sumG[1]*inverse(b[l])%P*v%P;
        xds[k].sumG[2]=xds[k].sumG[2]*inverse(b[l])%P*v%P;
        xds[k].sumG[3]=xds[k].sumG[3]*inverse(b[l])%P*v%P;
        return;
    }
    pushdown(k);
    if(z<=mid) ModifyB(l,mid,ls,z,v);
    else ModifyB(mid+1,r,rs,z,v);
    pushup(k);
}
ak Query(int l,int r,int k,int ll,int rr){
    if(l>=ll&&r<=rr) return xds[k].sumG[K];
    ak res=0;
    pushdown(k);
    if(ll<=mid) res=(res+Query(l,mid,ls,ll,rr)+P)%P;
    if(rr>mid) res=(res+Query(mid+1,r,rs,ll,rr)+P)%P;
    return res;
}
int main(){
    scanf("%d%d%lld%d",&n,&m,&p,&K);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    pi[0]=1;
    for(int i=1;i<=n;i++) pi[i]=pi[i-1]*p%P;
    for(int i=1;i<=n;i++) g[i]=(g[i-1]+pi[i]*a[i]%P)%P;
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    build(1,n,1);
    int op,c1;
    ak c2;
    while(m--){
        scanf("%d%d",&op,&c1);
        if(op==3) printf("%lld\n",Query(1,n,1,1,c1)%P);
        else{
            scanf("%lld",&c2);
            if(op==1){
                ModifyA(1,n,1,c1,n,pi[c1]*(c2-a[c1]+P)%P);
                a[c1]=c2;
            }else{
                ModifyB(1,n,1,c1,c2);
                b[c1]=c2;
            }
        }
    }
    return 0;
}