MYF

HDU 5068 Harry And Math Teacher

Posted on | In | | Visitors

题目链接

HDU 5068

题目类型：线段数

题目分析

题目大意

有n层楼，在魔法学校，每一层各有两个楼梯，无论你从哪一个楼梯都可以通往下一层，但是只能往上，不能往下。有的时候，楼梯会损毁，就无法通向下一层，但是有的时候又会自动修复。先给出楼层的数量n，以及m行信息，当第一个数字是0时，给出x和y，分别代表哈利波特现在所在的楼层和老师所在的楼层，查询哈利波特到达老师所在楼层的方法数。当的一个数字为1时，给出一个数字n和x，y，表示第n层的第x扇门通往第n+1层的第y扇门的楼梯坏了（如果本身是好的），表示第n层的第x扇门通往第n+1层的第y扇门的楼梯好了（如果本身是坏的）。

解析

手推一下，很容易发现规律，如果本层的楼梯和下面一层的楼梯都是好的的话，那么必然可以用矩阵来表示通网当前各门的情况数量。一开始很容易想到矩阵乘法，然后顺理成章的相当了矩阵快速幂，不过当其中间某几个楼梯是坏的的时候，要单独拎出来各段来计算，想法不太优越。如果能把这个问题转换为log(n)时间的更新和查询就好了，那么就很容易相当使用线段树，node[i]记录到达第i层的两扇门分别是从下面一层的每扇门传递过来的数量，这样将node[x]到node[y-1]累乘起来就是答案。根据线段树的性质，更新和查询效率都很高。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define pb push_back
#define mp make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=50000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
#define lson l,m,rt<<1          //预定子左树
#define rson m+1,r,rt<<1|1      //预定右子树
struct node {
    ll a[3][3];
    node(){
        memset(a, 0, sizeof(a));
    }
    void unit(){
        memset(a, 0, sizeof(a));
        a[1][1]=1;
        a[2][2]=1;
    }
    void one(){
        for(int i=1;i<=2;i++){
            for(int j=1; j<=2;j++){
                a[i][j]=1;
            }
        }
    }
    node operator *(const node &x){
        node rt;
        for(int i=1;i<=2;i++){
            for(int j=1; j<=2;j++){
                for(int k=1;k<=2;k++){
                    rt.a[i][j]=(rt.a[i][j]+a[i][k]*x.a[k][j]%mod)%mod;
                }
            }
        }
        return rt;
    }
    void show(){
        hi;
        for(int i=1;i<=2;i++){
            for(int j=1; j<=2;j++){
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
        hi;
    }
    ll sum(){
        ll ans=0;
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++){
                ans=(ans+a[i][j])%mod;
            }
        }
        return ans;
    }
}sum[maxn<<2];
void pushup(int rt){
    //对于编号为rt的节点，他的左右节点分别为rt<<1和rt<<1|1
    sum[rt]=sum[rt<<1]*sum[rt<<1|1];
}

//造树
void build(int l,int r,int rt){
    //建树操作，生成一个区间为l~r的完全二叉树
    
    //如果到底，则线段长度为0，表示一个点，输入该点的值
    if (l==r) {
        sum[rt].one();
        return;
    }
    
    //准备子树
    int m=(l+r)>>1;
    
    //对当前节点建立子树
    build(lson);
    build(rson);
    
    //由底向上求和
    pushup(rt);
}

//更新点和包含点的枝
void update(int pos,int l,int r,int rt){
    //pos为更新的位置 val为增加的值，正则加，负则减
    //l r为区间的两个端点值
    
    //触底，为一个点的时候，该节点值更新
    if (l==r) {
        int x,y;
        scanf("%d%d",&x,&y);
        sum[rt].a[x][y]^=1;
        return;
    }
    
    int m = ( l + r ) >> 1;
    
    if (pos<=m)     //pos在左子树的情况下，对左子树进行递归
        update(pos, lson);
    else            //pos在右子树的情况下，对右子树进行递归
        update(pos, rson);
    
    //更新包含该点的一系列区间的值
    pushup(rt);
}

//查询点或区间
node query(int L,int R,int l,int r,int rt){
    // L~R为被查询子区间 l~r为“当前”树的全区间
    
    if (L<=l&&r<=R)    //子区间包含“当前”树全区间
        return sum[rt]; //返回该节点包含的值
    int m=(l+r)>>1;
    node res;
    res.unit();
    if (L<=m)       //左端点在左子树内
        res=res*query(L, R, lson);
    if (R>m)        //右端点在右子树内
        res=res*query(L, R, rson);
    return res;
}
int main(){
    int n,m,op,x,y,pos;
    while (scanf("%d%d",&n,&m)!=EOF) {
        build(1, n, 1);
        for (int cas=0; cas<m; cas++) {
            scanf("%d",&op);
            if (op==0) {
                scanf("%d%d",&x,&y);
                node tmp = query(x, y-1, 1, n, 1);
//                tmp.show();
                cout<<tmp.sum()<<endl;
            }
            else{
                scanf("%d",&pos);
                update(pos, 1, n, 1);
            }
        }
    }
    return 0;
}