首页 > 代码库 > Hdu5068线段树

Hdu5068线段树

题意 :每层都有2个门,每个门后面都能通向下一层的两个门,有两个操作 ,第一个 问 从a层到 b层的方法数,第二个 修改 其中某门通向某门的状态。

 

线段树单点更新,就是 前面那个连通性矩阵有点厉害,看了题解才知道。

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include <math.h>using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1typedef long long LL;const LL maxn = 55555;const LL mod = 1000000007;struct Node{    LL x1, x2, x3, x4;};Node ans;Node node[maxn << 2];Node gao(Node a, Node b){    Node t;    t.x1 = a.x1*b.x1%mod + a.x2*b.x3%mod;    t.x2 = a.x1*b.x2%mod + a.x2*b.x4%mod;    t.x3 = a.x3*b.x1%mod + a.x4*b.x3%mod;    t.x4 = a.x3*b.x2%mod + a.x4*b.x4%mod;    return t;}void up(LL rt){    node[rt] = gao(node[rt<<1],node[rt<<1|1]);}void build(LL l, LL r, LL rt){    if (l == r){        node[rt].x1 = 1; node[rt].x2 = 1; node[rt].x3 = 1; node[rt].x4 = 1;        return;    }    LL mid = (l + r) >> 1;    build(lson);    build(rson);    up(rt);}void init(){    ans.x1 = 1; ans.x2 = 0; ans.x3 = 0; ans.x4 = 1;}void update(LL k, LL i, LL l, LL r, LL rt){    if (l == r){        switch (i){        case 1:node[rt].x1 ^= 1; break;        case 2:node[rt].x2 ^= 1; break;        case 3:node[rt].x3 ^= 1; break;            default:node[rt].x4 ^= 1;        }        return;    }    LL mid = (l + r) >> 1;    if (k <= mid) update(k, i, lson);    if (k > mid) update(k, i, rson);    up(rt);}void  ask(LL L, LL R, LL l, LL r, LL rt){    if (L <= l&&r <= R){        ans = gao(ans, node[rt]);        return;    }    LL mid = (l + r) >> 1;    if (L <= mid) ask(L, R, lson);    if (R > mid) ask(L, R, rson);}void output(){    LL sum;    sum = (ans.x1 + ans.x2)%mod + (ans.x3 + ans.x4)%mod;    sum%=mod;    printf("%I64d\n", sum);}int main(){    LL a, b, c, t, n, m;    while (cin >> n >> m){        build(1, n - 1, 1);        for (LL i = 0; i < m; i++){            scanf("%I64d", &t);            if (t == 0){                scanf("%I64d%I64d", &a, &b);                if (a == b){                    printf("0\n"); continue;                }                init();                ask(a, b - 1, 1, n - 1, 1);                output();            }            else{                scanf("%I64d%I64d%I64d", &a, &b, &c);                if (b == 1 && c == 1) update(a, 1, 1, n - 1, 1);                if (b == 1 && c == 2) update(a, 2, 1, n - 1, 1);                if (b == 2 && c == 1) update(a, 3, 1, n - 1, 1);                if (b == 2 && c == 2) update(a, 4, 1, n - 1, 1);            }        }    }    return 0;}

 

Hdu5068线段树