OI - Fibonacci-ish II(Codeforces)

线段树专题训练继续……了解到一个线段树存储矩阵的操作~

Part1. 题目

给出一个长度为 $n$ 的序列 $a_i$ 和一个整数 $mod$。

有 $m$ 次操作，每次操作给出区间 $[l,r]$：将 $a_l,a_{l+1}…a_r$ 从小到大排序、去重后得到序列 $b_1,b_2,…,b_k$，计算 $\sum_{i=1}^kb_i\times f_i$（其中 $f_i$ 是斐波那契数第 $i$ 项，$f_0=0,f_1=f_2=1$）。

（每次操作独立，即每次操作互不影响）

数据规模：$1\leq n,m,mod\leq30000$，$0\leq a_i\leq10^9$，$1\leq l\leq r\leq n$。

Part2. 解析

区间操作，$n\leq30000$……似乎 $O(n\sqrt n)$ 能过？于是想到可以莫队。

Part2/1. 莫队

先把 $a_i$ 离散化，然后 $a_i$ 就小于等于 $n$ 了。维护一个 cnt[i] 表示在当前区间（因为莫队其实是滑窗嘛）中数 i 出现的次数：这样如果收缩区间时数 i 出去了，就 cnt[i]--，如果扩大区间时 i 进入了区间，就 cnt[i]++。

于是我们可以知道：

当数 i 进入区间时，如果 i 之前没有在 $b_i$ 中，就把 i 插入 $b_i$（这样相当于去重）；
当数 i 离开区间时，如果删除 i 后，区间中没有 i 了，就在 $b_i$ 中删去 i。

那么我们就需要一个数据结构，来维护 $b_i$。

Part2/2. 矩阵

对于斐波那契数列，有一个广为人知的矩阵递推式：

$\begin{bmatrix}1&1\\1&0\end{bmatrix}\times\begin{bmatrix}f_i\\f_{i-1}\end{bmatrix}=\begin{bmatrix}f_{i+1}\\f_{i}\end{bmatrix}$

显然下式也成立：

$\begin{bmatrix}1&1\\1&0\end{bmatrix}\times\begin{bmatrix}kf_i\\kf_{i-1}\end{bmatrix}=\begin{bmatrix}kf_{i+1}\\kf_{i}\end{bmatrix}$

又因为矩阵乘法的分配律 $A(B+C)=AB+AC$。可以得到下式：

$\begin{bmatrix}1&1\\1&0\end{bmatrix}\times\begin{bmatrix}af_i+bf_j+cf_k\dots\\af_{i-1}+bf_{j-1}+cf_{k-1}\dots\end{bmatrix}=\begin{bmatrix}af_{i+1}+bf_{j+1}+cf_{k+1}\dots\\af_i+bf_j+cf_k\dots\end{bmatrix}$

Part2/3. 权值线段树

Part2/3/1. 维护节点信息

对于权值线段树维护的一个区间 $[l,r]$：设序列 $B_{l,r}=\{b_i | l\leq b_i\leq r\}$，则区间 $[l,r]$ 里存储的是：

$S_{l,r}$，$B_{l,r}$ 的大小；
一个矩阵 $M_{l,r}=\begin{bmatrix}\sum_{i=1}{B_{l,r}}[i]\times f_i\\\sum_{i=1}B_{l,r}[i]\times f_{i-1}\end{bmatrix}$，其中 $B_{l,r}[i]$ 指 $B_{l,r}[i]$ 中的第 $i$ 个元素。

那么对于一个线段树的节点 $[l,r]$ ，它的左儿子 $[l,m]$ 和右儿子 $[m+1,r]$ 可以这样合并起来：

$M_{l,r}=M_{l,m}+\begin{bmatrix}1&1\\1&0\end{bmatrix}^{S_{l,m}}\times M_{m+1,r}$

（应该比较直观吧）

这样的话，我们可以预处理出 $\begin{bmatrix}1&1\\1&0\end{bmatrix}^{k}$ ，然后就可以在常数时间（矩阵乘法的常数时间）内合并两个区间了~

Part2/3/2. 插入/删除元素

设插入元素 $i$：

我们就在线段树的区间 $[i,i]$ 处，将 $S_{i,i}$ 修改为 $1$，并且把 $M_{i,i}$ 修改为 $\begin{bmatrix}i\\0\end{bmatrix}$，然后向上更新节点信息直到根节点。

如果删除元素 $i$：

就把 $S_{i,i}$ 改为 $0$，$M_{i,i}$ 改为 $\begin{bmatrix}0\\0\end{bmatrix}$，向上更新节点信息即可。

Part2/3/3. 答案

最后根节点的信息就是当前整个序列的信息，即：

$M_{1,n}=\begin{bmatrix}\sum_{i=1}b_i\times f_i\\\sum_{i=1}b_i\times f_{i-1}\end{bmatrix}$

那么 $\sum_{i=1}b_i\times f_i$ 即是答案。

Part3. 源代码

注意取模是非常慢的……可以用减法代替取模，速度大概会快这么多：

/*Lucky_Glass*/
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3e4;

int n,m,Vper,Nl,Nr,Vmod,Vlim;
int Ia[N+3],Ecnt[N+3],Eans[N+3];
vector<int> Sra;
struct QUERY{int Cl,Cr,id;}qry[N+3];
struct MATRIX{
	int Vrol,Vcol;
	int Emat[3][3];
	MATRIX operator *(const MATRIX &B)const &{
		MATRIX Rr;
		Rr.Vrol=Vrol;Rr.Vcol=B.Vcol;
		for(int i=1;i<=Rr.Vrol;i++)
			for(int j=1;j<=Rr.Vcol;j++){
				Rr.Emat[i][j]=0;
				for(int k=1;k<=Vcol;k++){
					Rr.Emat[i][j]+=1ll*Emat[i][k]*B.Emat[k][j]%Vmod;
					if(Rr.Emat[i][j]>=Vmod) Rr.Emat[i][j]-=Vmod;
				}
			}
		return Rr;
	}
	MATRIX operator +(const MATRIX &B)const &{
		MATRIX Rr;
		Rr.Vrol=Vrol;Rr.Vcol=Vcol;
		for(int i=1;i<=Rr.Vrol;i++)
			for(int j=1;j<=Rr.Vcol;j++){
				Rr.Emat[i][j]=Emat[i][j]+B.Emat[i][j];
				if(Rr.Emat[i][j]>=Vmod) Rr.Emat[i][j]-=Vmod;
			}
		return Rr;
	}
}Mper,Mfeb[N+3];
struct SEGTREE{
	int Tnum[N*4];
	MATRIX Tmat[N*4];
	inline void PushUp(int u){
		Tnum[u]=Tnum[u<<1]+Tnum[u<<1|1];
		Tmat[u]=Tmat[u<<1]+Mfeb[Tnum[u<<1]]*Tmat[u<<1|1];
	}
	inline void Build(register int u,register int Vl,register int Vr){
		Tmat[u].Vcol=1;Tmat[u].Vrol=2;
		if(Vl==Vr) return;
		register int Vm=(Vl+Vr)>>1;
		Build(u<<1,Vl,Vm);
		Build(u<<1|1,Vm+1,Vr);
	}
	inline void Modify(register int u,register int Vl,register int Vr,register int Upos,register int Utmp){
		if(Vl==Vr){
			Tmat[u].Emat[1][1]=(Utmp*Sra[Vl-1]%Vmod+Vmod)%Vmod;
			Tmat[u].Emat[2][1]=0;
			Tnum[u]=Utmp;
			return;
		}
		register int Vm=(Vl+Vr)>>1;
		if(Upos<=Vm) Modify(u<<1,Vl,Vm,Upos,Utmp);
		else Modify(u<<1|1,Vm+1,Vr,Upos,Utmp);
		PushUp(u);
	}
}seg;

inline bool cmpQUERY(const QUERY Ca,const QUERY Cb){
	register int Ba=Ca.Cl/Vper,Bb=Cb.Cl/Vper;
	if(Ba==Bb)
		if(Ba&1) return Ca.Cr<Cb.Cr;
		else return Ca.Cr>Cb.Cr;
	else
		return Ca.Cl<Cb.Cl;
}
inline void NAdd(register int Vv){
	Ecnt[Ia[Vv]]++;
	if(Ecnt[Ia[Vv]]==1)
		seg.Modify(1,1,Vlim,Ia[Vv],1);
}
inline void NDelete(register int Vv){
	Ecnt[Ia[Vv]]--;
	if(Ecnt[Ia[Vv]]==0)
		seg.Modify(1,1,Vlim,Ia[Vv],0);
}
void Process(){
	Mper.Vcol=Mper.Vrol=2;
	Mper.Emat[1][1]=1;Mper.Emat[1][2]=1;
	Mper.Emat[2][1]=1;Mper.Emat[2][2]=0;
	Mfeb[0].Vcol=Mfeb[0].Vrol=2;
	Mfeb[0].Emat[1][1]=1;Mfeb[0].Emat[1][2]=0;
	Mfeb[0].Emat[2][1]=0;Mfeb[0].Emat[2][2]=1;
	for(register int i=1;i<=n;i++)
		Mfeb[i]=Mfeb[i-1]*Mper;
}
inline int fRead(){
	register int Vx=0;char Cc=getchar();
	while(Cc<'0' || '9'<Cc) Cc=getchar();
	while('0'<=Cc && Cc<='9') Vx=(Vx<<3)+(Vx<<1)+Cc-'0',Cc=getchar();
	return Vx;
}
int main(){
	n=fRead();Vmod=fRead(); 
	Process();
	for(register int i=1;i<=n;i++){
		Ia[i]=fRead();
		Sra.push_back(Ia[i]);
	}
	m=fRead();
	for(register int i=1;i<=m;i++){
		qry[i].Cl=fRead();qry[i].Cr=fRead();
		qry[i].id=i;
	}
	
	sort(Sra.begin(),Sra.end());
	Sra.erase(unique(Sra.begin(),Sra.end()),Sra.end());
	for(register int i=1;i<=n;i++) Ia[i]=lower_bound(Sra.begin(),Sra.end(),Ia[i])-Sra.begin()+1;
	
	Vper=ceil(sqrt(n));
	sort(qry+1,qry+1+m,cmpQUERY);
	
	Vlim=Sra.size();
	seg.Build(1,1,Vlim);
	
	Nl=1;
	for(register int i=1;i<=m;i++){
		while(Nr<qry[i].Cr) NAdd(++Nr);
		while(Nr>qry[i].Cr) NDelete(Nr--);
		while(Nl<qry[i].Cl) NDelete(Nl++);
		while(Nl>qry[i].Cl) NAdd(--Nl);
		Eans[qry[i].id]=seg.Tmat[1].Emat[1][1];
	}
	for(register int i=1;i<=m;i++)
		printf("%d\n",Eans[i]);
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问~