[CF 718C] Sasha and Array

传送门

Solution

用线段树维护矩阵

第一个操作相当于区间乘

第二个操作相当于区间求和

Code

#include<bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

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

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

#define mod 1000000007

#define MN 100005

#define mid ((l+r)>>1)

int n,m;

struct matrix

{

	ll a[2][2];

    matrix(){memset(a,0,sizeof a);}

    matrix operator *(const matrix &b) const

    {

        register matrix c;register int i,j,k;

        for(i=0;i<2;++i)for(j=0;j<2;j++)for(k=0;k<2;++k)

        (c.a[i][j]+=b.a[i][k]*a[k][j]%mod)%=mod;

        return c;

    }

    matrix operator +(const matrix &b) const

    {

    	register matrix c;register int i,j;

    	for(i=0;i<2;++i)for(j=0;j<2;++j) c.a[i][j]=(b.a[i][j]+a[i][j])%mod;

    	return c;

	}

}tmp,xxx,t[MN<<2],lazy[MN<<2],orig,pro,unit;

void fpow(int x)

{

	for(tmp=unit,xxx=pro;x;x>>=1,xxx=xxx*xxx) if(x&1) tmp=tmp*xxx;

}

void print(matrix x)

{

	for(int i=0;i<2;++i)

	{

		for(int j=0;j<2;++j) printf("%d ",x.a[i][j]);

		puts("");

	}

	puts("");

}

inline void pushdown(int x)

{

	t[x<<1]=t[x<<1]*lazy[x];t[x<<1|1]=t[x<<1|1]*lazy[x];

	lazy[x<<1]=lazy[x<<1]*lazy[x];lazy[x<<1|1]=lazy[x<<1|1]*lazy[x];

	lazy[x]=unit;

}

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

{

	if(l==r){fpow(read()-1),t[x]=orig*tmp,lazy[x]=unit;return;}

	build(x<<1,l,mid);build(x<<1|1,mid+1,r);

	t[x]=t[x<<1]+t[x<<1|1];lazy[x]=unit;

}

matrix query(int x,int l,int r,int a,int b)

{

	if(a==l&&r==b) return t[x];

	pushdown(x);

	if(b<=mid) return query(x<<1,l,mid,a,b);

	if(a>mid) return query(x<<1|1,mid+1,r,a,b);

	return query(x<<1,l,mid,a,mid)+query(x<<1|1,mid+1,r,mid+1,b);

}

void Modify(int x,int l,int r,int a,int b)

{

	if(a==l&&b==r){lazy[x]=lazy[x]*tmp,t[x]=t[x]*tmp;return;}

	pushdown(x);

	if(b<=mid) Modify(x<<1,l,mid,a,b);

	else if(a>mid) Modify(x<<1|1,mid+1,r,a,b);

	else Modify(x<<1,l,mid,a,mid),Modify(x<<1|1,mid+1,r,mid+1,b);

	t[x]=t[x<<1]+t[x<<1|1];

}

int main()

{

	unit.a[0][0]=unit.a[1][1]=1;

	orig.a[0][0]=1;

	pro.a[0][0]=pro.a[0][1]=pro.a[1][0]=1;

	n=read(),m=read();

	build(1,1,n);

	register int type,l,r;

	while(m--)

	{

		type=read();l=read();r=read();

		if(type==1) fpow(read()),Modify(1,1,n,l,r);

		else printf("%lld\n",query(1,1,n,l,r).a[0][0]);

	}

	return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

[CF 718C] Sasha and Array

传送门

Solution

Code

最新文章

热门文章