首页 > 代码库 > 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线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。