hdu 5068 线段树加+dp

这题说的是 有n 层每层 有两个门 每个门 可以到达上一层的两个门，然后求从a 层到达b 层的方案总数， 不能后退， 在同一层中不能从第一个门到达另一层

我们只要我们可以对于每个 区间内 有dp[o][2][2] , 表示 在这个区间中 从区间起始到达区间末尾 的两个门分别设 a1,a2, b1,b2, dp[o][0][0],和dp[o][0][1],表示从从a1到b1 和 a2 到 b1 的方案总数 然后同理dp[o][1][0]dp[o][1][1],

得到转移 通过线段树去优化他 得到转移 一旦ij 两地相通那么显然 i这个点 的 在前面这个区间的a1 a2 相应的乘上 后面 这个区间在 j 这个位置开始的方案总数， 得到他们在总区间结束时的在 b1上有多少个方案从前面区间的 a1 和a2 过来，通过这样得到整个区间的值

        for(int i=0; i<2; ++i)
            for(int j=0; j<2; ++j)
                if(star[mid][i][j]){
                  value[o].M[0][0]=(value[o].M[0][0] + value[o*2].M[i][0] * value[o*2+1].M[0][j] % mod )%mod;
                   value[o].M[0][1]=(value[o].M[0][1] + value[o*2].M[i][1] * value[o*2+1].M[0][j]%mod )%mod;
                   value[o].M[1][0]=(value[o].M[1][0] + value[o*2].M[i][0] * value[o*2+1].M[1][j]%mod )%mod;
                   value[o].M[1][1]=(value[o].M[1][1] + value[o*2].M[i][1] * value[o*2+1].M[1][j]%mod )%mod;

                }

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
typedef __int64 ll;
const int maxn = 50005;
const ll mod = 1000000007;
int loc,x,y;
struct Matx{
   ll M[2][2];
}P;
bool star[maxn+5][2][2];
void maintain(int mid ,Matx &A,Matx B){
         Matx ans;
         memset(ans.M,0,sizeof(ans.M));
           for(int i=0; i<2; ++i)
            for(int j=0; j<2; ++j)
                if(star[mid][i][j]){
                   ans.M[0][0]=(ans.M[0][0] + A.M[i][0] * B.M[0][j] )%mod;
                   ans.M[0][1]=(ans.M[0][1] + A.M[i][1] * B.M[0][j] )%mod;
                   ans.M[1][0]=(ans.M[1][0] + A.M[i][0] * B.M[1][j] )%mod;
                   ans.M[1][1]=(ans.M[1][1] + A.M[i][1] * B.M[1][j] )%mod;
                }
          for(int i=0; i<2; ++i)
            for(int j=0; j<2; ++j)
              A.M[i][j]=ans.M[i][j];
}
struct Itree{
    Matx value[maxn*4];

    void tain(int o,int mid){
         memset(value[o].M,0,sizeof(value[o].M));
           for(int i=0; i<2; ++i)
            for(int j=0; j<2; ++j)
                if(star[mid][i][j]){
                  value[o].M[0][0]=(value[o].M[0][0] + value[o*2].M[i][0] * value[o*2+1].M[0][j] % mod )%mod;
                   value[o].M[0][1]=(value[o].M[0][1] + value[o*2].M[i][1] * value[o*2+1].M[0][j]%mod )%mod;
                   value[o].M[1][0]=(value[o].M[1][0] + value[o*2].M[i][0] * value[o*2+1].M[1][j]%mod )%mod;
                   value[o].M[1][1]=(value[o].M[1][1] + value[o*2].M[i][1] * value[o*2+1].M[1][j]%mod )%mod;
                }
    }
    void build(int o, int L, int R){
         if(L==R){
           value[o].M[0][0]=1;
           value[o].M[0][1]=0;
           value[o].M[1][0]=0;
           value[o].M[1][1]=1;
             for(int i=0; i<2; ++i)
                for(int j=0; j<2;  ++j)
                  star[L][i][j]=true;
             return ;
         }
         int mid= (L+R)/2;
         build( o*2 , L , mid );
         build( o*2+1 , mid+1 , R );
         tain(o,mid);
    }

    void update(int o, int L, int R){
            if(L==R){
                star[L][x][y]=star[L][x][y]==false;
                return ;
            }
            int mid=(L+R)/2;
            if(loc<=mid) update(o*2,L,mid);
            else update(o*2+1,mid+1,R);
            tain(o, mid);
    }
    void query(int o, int L, int R){
            if( (L>=x&&R<=y) ){
                if(loc==0){
                    P=value[o];loc=1;
                }else{
                    maintain(L-1,P,value[o]);
                }
                return ;
            }
            int mid = (L+R)/2;
            if(x<=mid)
                query(o*2,L,mid);
            if(y>mid)
                query(o*2+1,mid+1,R);
    }
}T;
int main()
{
     int n,m;
     while(scanf("%d%d",&n,&m)==2){
        T.build(1,1,n);
        for(int i=0; i<m; ++i){
             loc=0;
             int op;
             scanf("%d",&op);
             if(op==0) {
                    scanf("%d%d",&x,&y);
                    T.query(1,1,n);
                    ll ans=0;
                    for(int i=0; i<2; ++i)
                         for(int j=0; j<2; ++j)
                          ans=(ans+ P.M[i][j])%mod;
                   printf("%I64d
",ans);
             }else{
                 scanf("%d%d%d",&loc,&x,&y);
                 x--; y--;
                 T.update(1,1,n);
             }
        }
     }
    return 0;
}