In this HackerEarth Zeus and Fibonacci problem solution, You are given an array A consisting of N integers. You have to process two types of queries on this array.
  1. Type 1: Change the ith element to X
  2. Type 2: Given l and r, calculate: Sigma(i=l,r)Sigma(j=i,r)Fib(Sigma(k=i,j) Ak)


HackerEarth Zeus and Fibonacci problem solution


HackerEarth Zeus and Fibonacci problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define maxn 100001

class Matrix
{
public:
int N;
int M[2][2];
Matrix() {}

Matrix(int _N)
{
N = _N;
memset(M, 0, sizeof M);
}
};
Matrix EMP(2),ID(2), FIB(2);
void gen()
{
ID.M[0][0] = ID.M[1][1] = 1;
FIB.M[1][1] = FIB.M[0][1] = FIB.M[1][0] = 1;
}

Matrix operator*(const Matrix &X, const Matrix &Y)
{
int N = X.N;
Matrix Z(N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
Z.M[i][j] += (X.M[i][k] * 1LL * Y.M[k][j]) % mod;
if (Z.M[i][j] >= mod)
Z.M[i][j] -= mod;
}
}
}
return Z;
}
Matrix operator^(Matrix X, ll power)
{
Matrix res = ID;
while (power)
{
if (power & 1)
res = res * X;
X = X * X;
power >>= 1;
}
return res;
}
Matrix operator+(Matrix X, const Matrix &Y)
{
for (int i = 0; i < X.N; i++)
{
for (int j = 0; j < X.N; j++)
{
X.M[i][j] = (X.M[i][j] + Y.M[i][j]);
if (X.M[i][j] >= mod) X.M[i][j] -= mod;
}
}
return X;
}
// fib(0)=0 fib(1)=1
// to calculate fib(n) take mat^(n)
ll arr[maxn];
Matrix ans[4*maxn],pre[4*maxn],suff[4*maxn],sum[4*maxn];


void build(ll node,ll a,ll b)
{
if(a==b)
{
ans[node]=FIB^(arr[a]);
pre[node]=FIB^(arr[a]);
suff[node]=FIB^(arr[a]);
sum[node]=FIB^(arr[a]);
return;
}
ll mid=(a+b)/2;
build(2*node,a,mid);
build(2*node+1,mid+1,b);

pre[node]=pre[2*node];
pre[node]=(pre[node]+(sum[2*node]*pre[2*node+1]));

suff[node]=suff[2*node+1];
suff[node]=(suff[node]+(sum[2*node+1]*suff[2*node]));

sum[node]=sum[2*node]*sum[2*node+1];

ans[node]=ans[2*node]+ans[2*node+1];
ans[node]=(ans[node]+(suff[2*node]*pre[2*node+1]));
}
void update(ll node,ll a,ll b,ll ind,ll val)
{
if(a>b || a>ind || b<ind)
return;
if(a==b)
{
ans[node]=FIB^val;
pre[node]=FIB^val;
suff[node]=FIB^val;
sum[node]=FIB^val;
return;
}
ll mid=(a+b)/2;
if(ind<=mid)
update(2*node,a,mid,ind,val);
else
update(2*node+1,mid+1,b,ind,val);

pre[node]=pre[2*node];
pre[node]=(pre[node]+(sum[2*node]*pre[2*node+1]));

suff[node]=suff[2*node+1];
suff[node]=(suff[node]+(sum[2*node+1]*suff[2*node]));

sum[node]=sum[2*node]*sum[2*node+1];

ans[node]=ans[2*node]+ans[2*node+1];
ans[node]=(ans[node]+(suff[2*node]*pre[2*node+1]));
}
pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > query(ll node,ll a,ll b,ll l,ll r)
{
if(a>b || a>r || b<l)
assert(false);
if(a>=l && b<=r)
return {{ans[node],sum[node]},{pre[node],suff[node]}};

ll mid=(a+b)/2;

if(mid<l)return query(2*node+1,mid+1,b,l,r);
else if(mid+1>r)return query(2*node,a,mid,l,r);

pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > p1=query(2*node,a,mid,l,r);
pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > p2=query(2*node+1,mid+1,b,l,r);
pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > p;

p.S.F=p1.S.F;
p.S.F=(p.S.F+(p1.F.S*p2.S.F));

p.S.S=p2.S.S;
p.S.S=(p.S.S+(p2.F.S*p1.S.S));

p.F.S=p1.F.S*p2.F.S;

p.F.F=p1.F.F+p2.F.F;
p.F.F=(p.F.F+(p1.S.S*p2.S.F));

return p;

}
int main()
{
boost1;boost2;
ll i,j,n,q,l,r,type,val,ind;
cin>>n;
assert(1<=n&&n<=100000);
gen();
for(i=1;i<=n;i++){
cin>>arr[i];
assert(1<=arr[i]&&arr[i]<=1000000000);
}

build(1,1,n);
cin>>q;
assert(1<=q&&q<=100000);
while(q--)
{
cin>>type;
assert(type==1||type==2);
if(type==1)
{
cin>>ind>>val;
assert(1<=ind&&ind<=n);
assert(1<=val&&val<=1000000000);
update(1,1,n,ind,val);
}
else
{
cin>>l>>r;
assert(l<=r&&1<=l&&l<=n&&1<=r&&r<=n);
Matrix temp=query(1,1,n,l,r).F.F;
assert(0<=((temp.M[0][1])%mod)&&((temp.M[0][1])%mod)<mod);
cout<<(temp.M[0][1])%mod<<endl;
}
}
return 0;
}