自动搬运

查看原文

来自洛谷，原作者为

	sane1981 2022CSP-J爆零 AFO 2024.11.30

搬运于2025-08-24 22:18:38，当前版本为作者最后更新于2023-07-31 11:34:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

背景

我最爱线段树了。

题目解读

原题传送门

首先我们发现 $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;
}