A，B，C傻逼题，就不说了。
E题：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=,mod=;
typedef long long int64;
int n,m,fuck[maxn<<];
int64 a[maxn],s1[maxn<<],s2[maxn<<];
struct Matrix{
int n,m;
int64 a[][];
void clear(){for (int i=;i<;i++)for (int j=;j<;j++)a[i][j]=;}
}wn,lazy[maxn<<],a0,t1,t2,b;
Matrix operator *(Matrix x,Matrix y){
Matrix ans; ans.n=x.n,ans.m=y.m;
ans.clear(); int N=ans.n,M=ans.m;
for (int i=;i<N;i++){
for (int j=;j<M;j++){
for (int k=;k<x.m;k++){
ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
}
}
}
return ans;
}
Matrix qpow(Matrix x,int64 y){
if (y==) return wn;
if (y==) return x;
Matrix d=qpow(x,y/); d=d*d;
if (y&) return d*x;
else return d;
}
void build(int k,int l,int r){
lazy[k]=wn; fuck[k]=-;
if (l==r) return;
int mid=(l+r)>>;
build(k*,l,mid),build(k*+,mid+,r);
}
void pushdown(int k,Matrix x){
Matrix y=x;
int64 oy=s1[k],zx=s2[k],A,B,C;
t1=a0*x; A=t1.a[][]; x=x*b;
t1=a0*x; B=t1.a[][]; x=x*b;
t1=a0*x; C=t1.a[][];
s1[k]=(oy*A%mod+zx*B%mod)%mod;
s2[k]=(oy*B%mod+zx*C%mod)%mod;
if (fuck[k]!=-){lazy[k]=lazy[k]*y,lazy[k]=lazy[k]*b;}
else lazy[k]=y;
fuck[k]=;
}
void insert(int k,int l,int r,int x,int64 y1,int64 y2){
if (l==r&&r==x){s1[k]=y1%mod,s2[k]=y2%mod;return;}
int mid=(l+r)>>;
if (x<=mid) insert(k*,l,mid,x,y1,y2);
else insert(k*+,mid+,r,x,y1,y2);
s1[k]=(s1[k*]+s1[k*+])%mod,s2[k]=(s2[k*]+s2[k*+])%mod;
}
void change(int k,int l,int r,int x,int y,Matrix t){
if (fuck[k]!=-){
if (l!=r){pushdown(k*,lazy[k]),pushdown(k*+,lazy[k]);}
lazy[k]=wn; fuck[k]=-;
}
if (l>=x&&r<=y){pushdown(k,t);return;}
int mid=(l+r)>>;
if (x<=mid) change(k*,l,mid,x,y,t);
if (y>mid) change(k*+,mid+,r,x,y,t);
s1[k]=(s1[k*]+s1[k*+])%mod,s2[k]=(s2[k*]+s2[k*+])%mod;
}
int64 query(int k,int l,int r,int x,int y){
if (fuck[k]!=-){
if (l!=r){pushdown(k*,lazy[k]),pushdown(k*+,lazy[k]);}
lazy[k]=wn; fuck[k]=-;
}
if (l>=x&&r<=y) return s2[k]%mod;
int mid=(l+r)>>; int64 temp=;
if (x<=mid) temp=(temp+query(k*,l,mid,x,y))%mod;
if (y>mid) temp=(temp+query(k*+,mid+,r,x,y))%mod;
return temp;
}
int main(){
scanf("%d%d",&n,&m); a0.clear(),t1.clear(),b.clear(),wn.clear();
a0.n=,a0.m=; a0.a[][]=,a0.a[][]=;
wn.n=,wn.m=;
for (int i=;i<;i++)
for (int j=;j<;j++){
if (i==j) wn.a[i][j]=;
else wn.a[i][j]=;
}
build(,,n);
b.n=b.m=;
for (int i=;i<;i++){
for (int j=;j<;j++){
if (!i&&!j) b.a[i][j]=;
else b.a[i][j]=;
}
}
memset(s1,,sizeof(s1));
memset(s2,,sizeof(s2));
for (int i=;i<=n;i++){
scanf("%I64d",&a[i]);
t1=a0*qpow(b,a[i]);
t2=a0*qpow(b,a[i]-);
insert(,,n,i,t2.a[][],t1.a[][]);
}
for (int type,l,r,x;m;m--){
scanf("%d%d%d",&type,&l,&r);
if (type==){
scanf("%d",&x);
t1=qpow(b,x-);
change(,,n,l,r,t1);
}else{printf("%I64d\n",query(,,n,l,r)%mod);}
}
return ;
}
链接：http://codeforces.com/contest/719/problem/E
题目大意：给定一个长度为n的序列ai，m个操作，有以下两种操作，1种是把l~r这一段数加上一个数x，另1种是询问l~r的f[ai]之和，f[i]为斐波那契数列的第i项，令f[1]=f[2]=1,f[i]=f[i-2]+f[i-1](i>2). n，m<=10^5 , 1<=ai，x<=10^9;
做法：这题显然是要用线段树和矩阵快速幂，但是是区间修改不好维护，但是对于斐波那契数列有个结论就是f[n+m]=f[n-1]*f[m]+f[n]*f[m+1],有了这个就很好做了，如下：
f(a+x) = f(x+1)f(a) + f(x)f(a-1)
f(a-1+x) = f(x-1)f(a-1) + f(x)f(a)
令s1(l,r)为区间内所有f(a[i])的和
令s2(l,r)为区间内所有f(a[i]-1)的和
然后线段树维护这两个就行了,每次计算某个f(x)的值就拿矩阵快速幂(8*logn)。
这样的做法是nlogn^2的，加上线段树的常数是过不了的，我们得考虑矩阵乘法那一部分，我们真的需要在每次传标记的时候都用logn的时间来计算f（x）吗，显然是不需要的，我们只要把lazy标记设为一个矩阵即可，为b^x（令b为用矩阵乘法求斐波那契数列时候的矩阵），合并标记的时候就把这个矩阵乘一下即可，总时间复杂度降为了nlogn，能过。这题首先用结论把问题转化为了支持区间修改，再利用了每次计算的重复，巧妙地把lazy标记定为矩阵，进一步降低时间复杂度，一个好题。