codeforces316E3 Summer Homework（线段树，斐波那契数列）

题目大意

给定一个n个数的数列，m个操作，有三种操作：

$1\ x\ v$ 将$a_x$的值修改成v

$2\ l\ r\ $ 求 $\sum_{i=l}^r x_i*f_{i-l}$ 其中对于$f$数组 $f_0=1\ ，f_1=1\ ，f_i=f_{i-1}+f_{i-2}$ （就是斐波那契数列）

$3\ l\ r\ x\ $ 让$a_i+x，i\in[l,r]$

其中$n\le 100000，m\le 100000$

一看这个题QwQ，就知道是线段树题

QwQ那么怎么维护节点信息和合并区间呢

来举个栗子试一下

对于系数分别为$1\ 1,1\ 2$来说

将二者相加变为$2\ 3$也就是以第三个元素开头的系数序列了~

由于fib序列相加还是fib序列

哇，那这么说，这个题目所给的求和的操作，也是可以通过已知矩阵乘转移矩阵快速得到目标矩阵

那么！就可以通过这个东西来转移了！

\[\begin{bmatrix}
0 & 1 \\
1& 1 \\
\end{bmatrix}
\]

所以！对于左右区间来说，合并的时候，只需要把右区间乘上左区间的长度次方（就相当于把右边这个区间的变为$f_{mid-l+1}$项开头）

同时，我们发现要进行矩阵转移，必须记录当前这个区间的元素从$f_0$开始和$f_1$开始的两个值，才能够进行矩阵计算

QwQ因为我不会矩阵乘法呀！

所以我是选择手动展开了矩阵的n次方

最后假设是求矩阵的n次方的话

那么最终的矩阵应为

\[\begin{bmatrix}
{fib}_{n-2} & {fib}_{n-1} \\
{fib}_{n-1}& {fib}_{n} \\
\end{bmatrix}
\]

~只需要预处理一下fib序列和fib序列的前缀和就行了

void up(int root)

{

	ll len = f[2*root].len;

	f[root].len=(f[2*root].len+f[2*root+1].len)%mod;

	f[root].fir=(f[2*root].fir+f[2*root+1].fir*get(len-2)+f[2*root+1].sec*fib[len-1])%mod;

	f[root].sec=(f[2*root].sec+f[2*root+1].fir*fib[len-1]+f[2*root+1].sec*fib[len])%mod;

}

接着，我们考虑，对3操作

如果让一个区间加x，就是让这个区间加x*fib前缀和的区间长度-1项（因为$f_0=1$）（求答案的是从$f_0$开始乘）

emmmm所以也是可以直接做了咯（记得从1开始乘的那个信息需要-add[root]）

void pushdown(int root,int l,int r)

{

	if (add[root])

	{

		add[2*root]=(add[2*root]+add[root])%mod;

		add[2*root+1]=(add[2*root+1]+add[root])%mod;

		f[2*root].fir=(f[2*root].fir+add[root]*sum[f[2*root].len-1])%mod;

		f[2*root].sec=(f[2*root].sec+add[root]*sum[f[2*root].len]-add[root])%mod;

		f[2*root+1].fir=(f[2*root+1].fir+add[root]*sum[f[2*root+1].len-1])%mod;

		f[2*root+1].sec=(f[2*root+1].sec+add[root]*sum[f[2*root+1].len]-add[root])%mod; //之所以-1是因为要减掉fib[0]

		add[root]=0;

	}

}

update和change和build都差不多~

需要注意的是！！！！！！！！！

query的时候，不能直接$return\ f[root].fir$

因为如果让区间为$[l,r]$，就需要将这一段嫁接到$[x,l-1]$的后面，对，所以也需要想之前合并的时候那样乘一个fib

if (x<=l && r<=y)

	{

		int len = l-1-x+1;

		if (len==0) return f[root].fir;

		return f[root].fir*get(len-2)+f[root].sec*get(len-1);

	}

其他的都差不多了啦

直接上代码！

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<map>

#include<vector>

#define ll long long

using namespace std;

inline ll read()

{

  ll x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 2e5+1e2;

const int mod = 1000000000;

struct Node

{

	ll fir,sec,len;

};

Node f[4*maxn];

ll add[4*maxn];

ll a[maxn];

ll fib[maxn],sum[maxn];

int n,m;

void init()

{

	fib[0]=1,fib[1]=1;

	for (int i=2;i<=n;i++) fib[i]=(fib[i-1]+fib[i-2])%mod;

	sum[0]=1;

	for (int i=1;i<=n;i++) sum[i]=(sum[i-1]+fib[i])%mod;

}

ll get(int x)

{

	if (x<0) return 0;

	else return fib[x];

}

void up(int root)

{

	ll len = f[2*root].len;

	f[root].len=(f[2*root].len+f[2*root+1].len)%mod;

	f[root].fir=(f[2*root].fir+f[2*root+1].fir*get(len-2)+f[2*root+1].sec*fib[len-1])%mod;

	f[root].sec=(f[2*root].sec+f[2*root+1].fir*fib[len-1]+f[2*root+1].sec*fib[len])%mod;

}

void pushdown(int root,int l,int r)

{

	if (add[root])

	{

		add[2*root]=(add[2*root]+add[root])%mod;

		add[2*root+1]=(add[2*root+1]+add[root])%mod;

		f[2*root].fir=(f[2*root].fir+add[root]*sum[f[2*root].len-1])%mod;

		f[2*root].sec=(f[2*root].sec+add[root]*sum[f[2*root].len]-add[root])%mod;

		f[2*root+1].fir=(f[2*root+1].fir+add[root]*sum[f[2*root+1].len-1])%mod;

		f[2*root+1].sec=(f[2*root+1].sec+add[root]*sum[f[2*root+1].len]-add[root])%mod; //之所以-1是因为要减掉fib[0]

		add[root]=0;

	}

}

void build(int root,int l,int r)

{

	if (l==r)

	{

		f[root].sec=f[root].fir=a[l]%mod;

		f[root].len=1;

		return;

	}

	int mid = (l+r) >> 1;

	build(2*root,l,mid);

	build(2*root+1,mid+1,r);

	up(root);

}

void update(int root,int l,int r,int x,int y,int p)

{

	if (x<=l && r<=y)

	{

		add[root]=(add[root]+p)%mod;

		f[root].fir=(f[root].fir+sum[r-l]*p)%mod;

		f[root].sec=(f[root].sec+sum[r-l+1]*p-p)%mod;

		return;

	}

	pushdown(root,l,r);

	int mid = (l+r) >> 1;

	if (x<=mid) update(2*root,l,mid,x,y,p);

	if (y>mid) update(2*root+1,mid+1,r,x,y,p);

	up(root);

}

void change(int root,int l,int r,int x,int p)

{

	if (l==r)

	{

		f[root].fir=f[root].sec=p%mod;

		add[root]=0;

		f[root].len=1;

		return;

	}

	pushdown(root,l,r);

	int mid = (l+r) >> 1;

	if (x<=mid) change(2*root,l,mid,x,p);

	if (x>mid) change(2*root+1,mid+1,r,x,p);

	up(root);

}

ll query(int root,int l,int r,int x,int y)

{

	if (x<=l && r<=y)

	{

		int len = l-1-x+1;

		if (len==0) return f[root].fir;

		return f[root].fir*get(len-2)+f[root].sec*get(len-1);

	}

	int mid = (l+r) >> 1;

	pushdown(root,l,r);

	ll ans=0;

	if (x<=mid) ans=(ans+query(2*root,l,mid,x,y))%mod;

	if (y>mid) ans=(ans+query(2*root+1,mid+1,r,x,y))%mod;

	return ans%mod;

}

int main()

{

  scanf("%d%d",&n,&m);

  init();

  for (int i=1;i<=n;i++) a[i]=read();

  build(1,1,n);

  //cout<<query(1,1,n,1,4)<<endl;

  for (int i=1;i<=m;i++)

  {

  	 int opt;

  	 opt=read();

  	 if (opt==1)

  	 {

  	 	int x=read();

		ll y=read();

  	 	change(1,1,n,x,y);

	   }

	if (opt==2)

	{

		int x=read(),y=read();

		//cout<<x<<" "<<y<<endl;

		printf("%lld\n",query(1,1,n,x,y));

		//cout<<query(1,1,n,1,4)<<endl;

	}

	if (opt==3)

	{

		int x=read(),y=read();

		ll z=read();

		update(1,1,n,x,y,z);

	}

  }

  return 0;

}

巴特西

codeforces316E3 Summer Homework（线段树，斐波那契数列）

最新文章

热门文章