自动搬运

查看原文

来自洛谷，原作者为

	SDNetFriend 路漫漫其修远兮，吾将上下而求索 | AFO

搬运于2025-08-24 21:47:46，当前版本为作者最后更新于2022-03-15 21:37:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

从某位不愿透露姓名的神仙处获得了一个做法。

一种线段树配合矩阵乘法的做法。

首先看到这个线性递推式子，显然可以直接矩阵快速幂没有什么问题，就把向量设为形如 $F_i,F_{i-1},1$ 就可以了，我们叫这个向量是 $V(i)$，然后我们设使得 $i$ 加一的转移矩阵为 $pl$，减一的为 $mi$。

然后看，最终我们计算贡献的式子是：$F_{A_{i-1}+1}F_{A_{i+1}-1}$。

我们可以发现，如果按照我们写代码时，把向量放进矩阵里面，假设 $V$ 是列向量，那么转置就是个行向量。用这两个对应的矩阵，列向量左乘行向量得到的结果就恰好是两个向量第一位之积。

那么这个乘积就可以描述成 $(V(A_{i-1}+1)\times V(A_{i+1}-1)^T)[0][0]$ 的，这个东西有什么用呢？我们设 $W(i)=V(A_{i-1}+1)\times V(A_{i+1}-1)^T$

我们考虑对一个点 $i$，我们都维护一下 $W(i)$。这样有什么用呢？假设我想要让 $A_{i-1}$ 和 $A_{i+1}$ 都加上 $1$，那么新的贡献一定可以通过 $((pl\times V(A_{i-1}+1))\times (pl\times V(A_{i+1}-1))^T)[0][0]=(pl\times W(i)\times pl^T)[0][0]$ 表示出来。

那此时使用线段树的思路就明了了，因为矩阵乘法对加法具有分配律，所以我们线段树维护区间 $W$ 之和，然后修改的时候直接整体在前面或者后面乘上转移矩阵，就可以得出答案了！形式化地写，即：（以左右均乘加一矩阵为例）

$$pl\times (\sum_{i=l}^r W(i))\times pl^T=\sum_{i=l}^r pl\times W(i)\times pl^T $$

于是本题解决了，时间复杂度 $O((n+Q)\log n)$。

另外不知道为什么这个题直接写普通线段树会 TLE，但如果写动态开点就能过，很迷惑。

代码

#include <bits/stdc++.h>
#define lint long long
using namespace std;
inline int read(){
	char c;int f=1,res=0;
	while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return res*f;
}
const int N=3e5+5;
const lint md=1e9+7;
#define add(x,y) x=(x+y)%md
struct mat{
	lint v[3][3];
	mat(lint x=0){
		memset(v,0,sizeof v);
		for(int i=0;i<3;++i)v[i][i]=x;
	}inline lint* operator[](int x)
		{return v[x];}
	inline mat operator*(mat x){
		mat r;
		for(int i=0;i<3;++i)
			for(int k=0;k<3;++k)
				for(int j=0;j<3;++j)
					add(r[i][j],v[i][k]*x[k][j]);
		return r;
	}inline mat operator+(mat x){
		for(int i=0;i<3;++i)
			for(int j=0;j<3;++j)
				add(x[i][j],v[i][j]);
		return x;
	}inline mat T(){
		mat r;
		for(int i=0;i<3;++i)
			for(int j=0;j<3;++j)
				r[i][j]=v[j][i];
		return r;
	}inline mat qpow(lint x){
		mat r(1),t=*this;
		while(x){
			if(x&1)r=r*t;
			t=t*t;x>>=1;
		}return r;
	}
}pl,mi,tpl,tmi,f,tf;
int n,nq;lint a,b,v[N];
inline lint qpow(lint x,lint y=md-2){
	lint res=1;
	while(y){
		if(y&1)res=res*x%md;
		x=x*x%md;y>>=1;
	}return res;
}
inline void init(){
	pl[0][0]=pl[1][0]=pl[2][2]=1;
	pl[0][1]=a;pl[0][2]=b;
	f[0][0]=2;f[1][0]=f[2][0]=1;
	tpl=pl.T();tf=f.T();
	if(a){
		mi[0][1]=mi[2][2]=1;
		mi[1][0]=qpow(a);
		mi[1][1]=md-qpow(a);
		mi[1][2]=md-b*qpow(a)%md;
	}else{
		mi[0][1]=mi[1][1]=mi[2][2]=1;
		mi[1][2]=md-b;
	}tmi=mi.T();
}
mat s[N<<1],tl[N<<1],tr[N<<1];
int ch[N<<1][2],tot,rt;
inline void nupd(int x,mat lu,mat ru){
	tl[x]=lu*tl[x];tr[x]=tr[x]*ru;
	s[x]=lu*s[x]*ru;
}inline void pushdown(int x){
	nupd(ch[x][0],tl[x],tr[x]);
	nupd(ch[x][1],tl[x],tr[x]);
	tl[x]=tr[x]=mat(1);
}void build(int &x=rt,int l=2,int r=n-1){
	x=++tot;tl[x]=tr[x]=mat(1);
	if(l==r){
		s[x]=pl.qpow(v[l-1]-1)*f;
		s[x]=s[x]*tf*tpl.qpow(v[l+1]-3);
		return;
	}int mid=l+r>>1;
	build(ch[x][0],l,mid);
	build(ch[x][1],mid+1,r);
	s[x]=s[ch[x][0]]+s[ch[x][1]];
}
void upd(int lp,int rp,mat lu,mat ru,int x=rt,int l=2,int r=n-1){
	if(l>rp||r<lp)return;
	if(lp<=l&&r<=rp)return nupd(x,lu,ru);
	int mid=l+r>>1;pushdown(x);
	upd(lp,rp,lu,ru,ch[x][0],l,mid);
	upd(lp,rp,lu,ru,ch[x][1],mid+1,r);
	s[x]=s[ch[x][0]]+s[ch[x][1]];
}
mat query(int lp,int rp,int x=rt,int l=2,int r=n-1){
	if(l>rp||r<lp)return mat();
	if(lp<=l&&r<=rp)return s[x];
	int mid=l+r>>1;pushdown(x);
	mat res=query(lp,rp,ch[x][0],l,mid);
	res=res+query(lp,rp,ch[x][1],mid+1,r);
	return res;
}
int main(){
	n=read();nq=read();
	a=read();b=read();
	for(int i=1;i<=n;++i)v[i]=read();
	init();build();
	while(nq--){
		string op;cin>>op;
		int l=read(),r=read();
		if(op=="plus"){
			upd(l+1,r+1,pl,mat(1));
			upd(l-1,r-1,mat(1),tpl);
		}else if(op=="minus"){
			upd(l+1,r+1,mi,mat(1));
			upd(l-1,r-1,mat(1),tmi);
		}else if(op=="query")
			printf("%lld\n",query(l+1,r-1)[0][0]);
	}return 0;
}