题目链接：http://codeforces.com/problemset/problem/316/E3
题意：一个数列A三种操作：（1）1 x y将x位置的数字修改为y；（2）2 x y求[x,y]区间的数字的和，和函数为如下；（3）3 x y z将[x,y]区间的数字统一加z。
思路：很明显，这是一个线段树的题目。其中第一种和第三种操作都很容易搞定，第一种直接更新到底；第三种增加标记。显然为了求和，我们必须要在节点上增加一个和，表示以这个节点为根的子树的数字的和函数，这里我们用a来表示。那么，到这里有两件事情要解决：
（1）如何在区间增加一个值x时更新a？设该区间为[L,R]，则增加的和为：
（2）已知两段数字的和函数，如何拼接成一个和函数？设前一段为3，后一段为4，那么我们要将后一段修改，修改前为：
修改后为：
为了方便，我们先看看怎么把（1,1,2,3）变为（1,2,3,5），也就是：
其实就是：
我们用a表示某段内（设这一段有x个数）x个数的和函数，b表示后x-1个数的和函数，那么上面其实就是a+b，得到A，那么B怎么得到呢？（AB和ab对应，我们发现B=a），因此我们得到转移矩阵：
注意这个的b和B是为了方便计算我们要新加到线段树节点中的值。那么上面(1,1,2,3)到(3,5,8,13)的转变岂不是成了：
到这里，我们就解决了两段和函数拼成一段的方法。
struct Matrix
{
i64 a[2][2];
void init(int x)
{
clr(a,0);
if(x==1) a[0][0]=a[1][1]=1;
else if(x==2) a[0][0]=a[0][1]=a[1][0]=1;
}
Matrix operator*(Matrix p)
{
Matrix ans;
ans.init(0);
int i,j,k;
FOR0(k,2) FOR0(i,2) FOR0(j,2)
{
ans.a[i][j]+=a[i][k]*p.a[k][j];
ans.a[i][j]%=mod;
}
return ans;
}
};
Matrix A[N];
i64 f[N];
void init()
{
A[0].init(1);
A[1].init(2);
int i;
for(i=2;i<N;i++) A[i]=A[i-1]*A[1];
f[0]=f[1]=1;
for(i=2;i<N;i++) f[i]=(f[i-1]+f[i-2])%mod;
for(i=1;i<N;i++) f[i]=(f[i]+f[i-1])%mod;
}
struct node
{
int L,R;
i64 a,b,flag;
node(){}
node(i64 _a,i64 _b)
{
a=_a;
b=_b;
}
node det(int t)
{
i64 x=(a*A[t].a[0][0]+b*A[t].a[0][1])%mod;
i64 y=(a*A[t].a[1][0]+b*A[t].a[1][1])%mod;
return node(x,y);
}
void add(i64 x)
{
flag=(flag+x)%mod;
a=(a+f[R-L]*x)%mod;
if(R>L) b=(b+f[R-L-1]*x)%mod;
}
node operator+(node p)
{
i64 x=(a+p.a)%mod,y=(b+p.b)%mod;
return node(x,y);
}
};
node a[N<<2];
int b[N];
void pushUp(int t)
{
if(a[t].L==a[t].R) return;
int mid=(a[t].L+a[t].R)>>1;
node temp=a[t*2+1].det(mid-a[t].L+1);
a[t].a=(a[t*2].a+temp.a)%mod;
a[t].b=(a[t*2].b+temp.b)%mod;
}
void pushDown(int t)
{
if(a[t].L==a[t].R) return;
if(a[t].flag)
{
a[t*2].add(a[t].flag);
a[t*2+1].add(a[t].flag);
a[t].flag=0;
}
}
void build(int t,int L,int R)
{
a[t].L=L;
a[t].R=R;
a[t].flag=a[t].b=0;
if(L==R)
{
a[t].a=b[L];
return;
}
int mid=(a[t].L+a[t].R)>>1;
build(t*2,L,mid);
build(t*2+1,mid+1,R);
pushUp(t);
}
void change(int t,int pos,int x)
{
if(a[t].L==a[t].R)
{
a[t].a=x;
a[t].b=0;
a[t].flag=0;
return;
}
pushDown(t);
int mid=(a[t].L+a[t].R)>>1;
if(pos<=mid) change(t*2,pos,x);
else change(t*2+1,pos,x);
pushUp(t);
}
void change(int t,int L,int R,int x)
{
if(a[t].L==L&&a[t].R==R)
{
a[t].add(x);
return;
}
pushDown(t);
int mid=(a[t].L+a[t].R)>>1;
if(R<=mid) change(t*2,L,R,x);
else if(L>mid) change(t*2+1,L,R,x);
else
{
change(t*2,L,mid,x);
change(t*2+1,mid+1,R,x);
}
pushUp(t);
}
node query(int t,int L,int R)
{
if(a[t].L==L&&a[t].R==R) return a[t];
pushDown(t);
node A,B;
int mid=(a[t].L+a[t].R)>>1;
if(R<=mid) A=query(t*2,L,R);
else if(L>mid) A=query(t*2+1,L,R);
else
{
A=query(t*2,L,mid);
B=query(t*2+1,mid+1,R);
A=A+B.det(mid-L+1);
}
pushDown(t);
return A;
}
int n,m;
int main()
{
init();
Rush(n)
{
RD(m);
int i;
FOR1(i,n) RD(b[i]);
build(1,1,n);
int op,x,y,z;
while(m--)
{
RD(op);
if(op==1)
{
RD(x,y);
change(1,x,y);
}
else if(op==2)
{
RD(x,y);
PR(query(1,x,y).a);
}
else
{
RD(x,y,z);
change(1,x,y,z);
}
}
}
}