codeforces316E3

Summer Homework

 CodeForces - 316E3 

By the age of three Smart Beaver mastered all arithmetic operations and got this summer homework from the amazed teacher:

You are given a sequence of integers a₁, a₂, ..., a_n. Your task is to perform on it mconsecutive operations of the following type:

1. For given numbers x_i and v_i assign value v_i to element a_xi.
2. For given numbers l_i and r_i you‘ve got to calculate sum , where f₀ = f₁ = 1 and at i ≥ 2: f_i = f_i - 1 + f_i - 2.
3. For a group of three numbers l_i r_i d_i you should increase value a_x by d_i for all x (l_i ≤ x ≤ r_i).

Smart Beaver planned a tour around great Canadian lakes, so he asked you to help him solve the given problem.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2·10⁵) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁵). Then follow m lines, each describes an operation. Each line starts with an integer t_i (1 ≤ t_i ≤ 3) — the operation type:

• if t_i = 1, then next follow two integers x_i v_i (1 ≤ x_i ≤ n, 0 ≤ v_i ≤ 10⁵);
• if t_i = 2, then next follow two integers l_i r_i (1 ≤ l_i ≤ r_i ≤ n);
• if t_i = 3, then next follow three integers l_i r_i d_i (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ d_i ≤ 10⁵).

The input limits for scoring 30 points are (subproblem E1):

• It is guaranteed that n does not exceed 100, m does not exceed 10000 and there will be no queries of the 3-rd type.

The input limits for scoring 70 points are (subproblems E1+E2):

• It is guaranteed that there will be queries of the 1-st and 2-nd type only.

The input limits for scoring 100 points are (subproblems E1+E2+E3):

• No extra limitations.

Output

For each query print the calculated sum modulo 1000000000 (10⁹).

Examples

Input

5 5
1 3 1 2 4
2 1 4
2 1 5
2 2 4
1 3 10
2 1 5

Output

12
32
8
50

Input

5 4
1 3 1 2 4
3 1 4 1
2 2 4
1 2 10
2 1 5

Output

12
45

 

sol：对于斐波那契数列，是有矩阵的递推公式的，搬一个讲的很好的blog

 

自己手撸一下，发现法2转移其实很好理解
如这样一个数列
              1,2,3,4
斐波那契数列是1 1 2 3 5
S[0](1~2)是1*f[0]+2*f[1] S[1](1~2)是1*f[1]+2*f[2]
S[0](3~4)是3*f[0]+4*f[1] S[1](1~2)是3*f[1]+4*f[2]
转移S[0](1~4)是1*f[0]+2*f[1]+3*(f[0]*f[0]+f[1]*f[1])+4*(f[1]*f[0]+f[2]*f[1])
假如把这些看成矩阵乘法
这个例子太low了看个大一点的
数列1,2,3,4,5,6,7,8
S[0](1,8)直接看后面的
5*(f[0]*f[2]+f[1]*f[3])+6*(f[1]*f[2]+f[2]*f[3])+7*(f[2]*f[2]+f[3]*f[3])+8*(f[3]*f[2]+f[4]*f[3])

然后机智的发现f[0]=f[1]=1，所以f[0]*f[2]+f[1]*f[3]=f[4]  容易知道f[0]*矩阵k=f[1] f[1]*矩阵k=f[2] 所以f[1]*f[2]+f[2]*f[3]就是f[4]*矩阵k=f[5]

容易发现f[0]*f[2]+f[1]*f[3]=f[4] f[1]*f[2]+f[2]*f[3]=f[5] 这样就做完了qaq
k=1 1
  1 0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0; bool f=0; char ch=‘ ‘;
    while(!isdigit(ch)) {f|=(ch==‘-‘); ch=getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0) {putchar(‘-‘); x=-x;}
    if(x<10) {putchar(x+‘0‘); return;}
    write(x/10); putchar((x%10)+‘0‘);
}
#define W(x) write(x),putchar(‘ ‘)
#define Wl(x) write(x),putchar(‘\n‘)
const int N=200005;
const ll Mod=1000000000;
int n,m;
ll a[N],f[N],fs[N];
inline int fei(int x){if(x<0)return 0;else return f[x];}
struct Node
{
    ll le,S[2],lazy;
}T[N<<2];
#define c1 (x<<1)
#define c2 (x<<1|1)
inline ll Ad(ll x,ll y) {x+=y; x-=(x>=Mod)?Mod:0; x+=(x<0)?Mod:0; return x;}
inline ll Ad(ll x,ll y,ll z){return Ad(Ad(x,y),z);}
inline ll Mul(ll x,ll y) {return 1ll*x*y%Mod;}
inline Node Merg(Node a,Node b)
{
    Node ans;
    ans.le=a.le+b.le; ans.lazy=0;
    ans.S[0]=Ad(a.S[0],Mul(b.S[0],fei(a.le-2)),Mul(b.S[1],fei(a.le-1)));
    ans.S[1]=Ad(a.S[1],Mul(b.S[0],fei(a.le-1)),Mul(b.S[1],fei(a.le)));
    return ans;
}
inline void F5(Node &a,ll oo)
{
    a.S[0]=Ad(a.S[0],Mul(oo,fs[a.le-1]));
    a.S[1]=Ad(a.S[1],Ad(Mul(oo,fs[a.le]),-oo));
}
inline void PushDown(int x)
{
    if(!T[x].lazy) return;
    T[c1].lazy=Ad(T[c1].lazy,T[x].lazy); F5(T[c1],T[x].lazy);
    T[c2].lazy=Ad(T[c2].lazy,T[x].lazy); F5(T[c2],T[x].lazy);
    T[x].lazy=0;
}
inline void Build(int x,int l,int r)
{
    T[x].le=r-l+1; T[x].lazy=0;
    if(l==r)
    {
        T[x].S[0]=T[x].S[1]=a[l]; return;
    }
    int mid=(l+r)>>1;
    Build(c1,l,mid); Build(c2,mid+1,r);
    T[x]=Merg(T[c1],T[c2]);
}
inline void Chag(int x,int l,int r,int Pos,ll Val)
{
    if(l==r)
    {
        T[x].S[0]=T[x].S[1]=Val; return;
    }
    PushDown(x);
    int mid=(l+r)>>1;
    if(Pos<=mid) Chag(c1,l,mid,Pos,Val);
    else Chag(c2,mid+1,r,Pos,Val);
    T[x]=Merg(T[c1],T[c2]);
}
inline Node Que(int x,int l,int r,int ql,int qr)
{
//    cout<<l<<‘ ‘<<r<<‘ ‘<<ql<<‘ ‘<<qr<<" "<<T[x].S[0]<<endl;
    if(ql==l&&qr==r) return T[x];
    PushDown(x);
    int mid=(l+r)>>1;
    if(qr<=mid) return Que(c1,l,mid,ql,qr);
    else if(ql>mid) return Que(c2,mid+1,r,ql,qr);
    else return Merg(Que(c1,l,mid,ql,mid),Que(c2,mid+1,r,mid+1,qr));
    T[x]=Merg(T[c1],T[c2]);
}
inline void Updata(int x,int l,int r,int ql,int qr,ll Val)
{
    if(ql==l&&qr==r)
    {
        T[x].lazy=Ad(T[x].lazy,Val); F5(T[x],Val); return;
    }
    PushDown(x);
    int mid=(l+r)>>1;
    if(qr<=mid) Updata(c1,l,mid,ql,qr,Val);
    else if(ql>mid) Updata(c2,mid+1,r,ql,qr,Val);
    else Updata(c1,l,mid,ql,mid,Val),Updata(c2,mid+1,r,mid+1,qr,Val);
    T[x]=Merg(T[c1],T[c2]);
}
int main()
{
    int i;
    R(n); R(m);
    for(i=1;i<=n;i++) R(a[i]);
    f[0]=f[1]=1; for(i=2;i<=n;i++) f[i]=Ad(f[i-1],f[i-2]);
    fs[0]=1; for(i=1;i<=n;i++) fs[i]=Ad(fs[i-1],f[i]);
    Build(1,1,n);
//    cout<<"!!!!"<<Que(1,1,n,4,4).S[0]<<endl;
//    return 0;
    while(m--)
    {
        int opt; ll x,y,z; R(opt); R(x); R(y);
        if(opt==1)
        {
            Chag(1,1,n,x,y);
        }
        else if(opt==2)
        {
            if(x>y) swap(x,y);
            Node ans=Que(1,1,n,x,y); Wl(ans.S[0]);
        }
        else if(opt==3)
        {
            R(z); Updata(1,1,n,x,y,z);
        }
    }
    return 0;
}
/*
Input
5 5
1 3 1 2 4
2 1 4
2 1 5
2 2 4
1 3 10
2 1 5
Output
12
32
8
50
 
Input
5 4
1 3 1 2 4
3 1 4 1
2 2 4
1 2 10
2 1 5
Output
12
45
*/

View Code