hdu 5068 线段树维护矩阵乘积

http://acm.hdu.edu.cn/showproblem.php?pid=5068

题意给的略不清晰

m个询问：从i层去j层的方法数(求连段乘积)或者修改从x层y门和x+1层z门的状态反转(更新只需更新一个节点的矩阵)

直接贴题解

我们可以把第i层跟第i+1层之间楼梯的通断性构造成一个2*2的通断性矩阵，1表示通，0表示不通。那么从第a层到第b层，就是将a到b-1的通断性矩阵连乘起来，然后将得到的答案矩阵上的每个元素加起来即为方案数。想到矩阵的乘法是满足结合律的，那么我们可以用线段树来维护矩阵的乘积。每次我们只会修改某一个楼梯的通断性，所以就只是简单的线段树单点更新，成段求乘积而已。
整体复杂度2∗2∗2∗nlogn

线段树维护矩阵乘积

初始化时要当成所有门是完好的

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
const int maxn = 30010;
#define M 50005
#define N 11
#define P 1000000007
using namespace std;
struct node{
int L,R;
int num[2][2];
}tree[M<<2];
void up(node &A,node &B,node &C){
int i,j,k;
for(i=0;i<2;i++)
for(j=0;j<2;j++){
A.num[i][j]=0;
for(k=0;k<2;k++){
A.num[i][j]+=(1LL*B.num[i][k]*C.num[k][j])%P;
}
A.num[i][j]%=P;
}
}
void build(int L,int R,int p){
tree[p].L=L,tree[p].R=R;
if(L==R){
tree[p].num[0][0]=1; tree[p].num[0][1]=1;
tree[p].num[1][0]=1; tree[p].num[1][1]=1;
return;
}
int mid=(L+R)>>1;
build(L,mid,2*p);
build(mid+1,R,2*p+1);
up(tree[p],tree[2*p],tree[2*p+1]);
}
node query(int L,int R,int p){
if(tree[p].L==L&&tree[p].R==R){
return tree[p];
}
int mid=(tree[p].L+tree[p].R)>>1;
if(R<=mid)return query(L,R,2*p);
else if(L>mid)return query(L,R,2*p+1);
else{
node tmp1=query(L,mid,2*p);
node tmp2=query(mid+1,R,2*p+1);
node res;
up(res,tmp1,tmp2);
return res;
}
}
void update(int x,int a,int b,int p){
if(tree[p].L==tree[p].R){
tree[p].num[a][b]^=1;
return ;
}
int mid=(tree[p].L+tree[p].R)>>1;
if(x<=mid)update(x,a,b,2*p);
else update(x,a,b,2*p+1);
up(tree[p],tree[2*p],tree[2*p+1]);
}
int main(){
int n,m,i,j,k,a,b,x,y,z;
while(~RD2(n,m)){
build(1,n-1,1);
while(m--){
RD(k);
if(k==0){
RD2(a,b);
node res=query(a,b-1,1);
int ans=(1LL*res.num[0][0]+res.num[0][1]+res.num[1][0]+res.num[1][1])%P;
printf("%d\n",ans);
}else{
RD3(x,y,z);
update(x,y-1,z-1,1);
}
}
}
return 0;
}