【hdu5068】Harry And Math Teacher

2015.05.23 16:24 Sat | 12次阅读 | 旧日oi | 固定链接 | 源码

题目大意:n层楼,每层楼有两个门,互不相连,第i层和第i+1层的两个门之间互相连接,也就是有4条路,可以实时改变一些路的通断,询问从第x层到第y层的路径数,对10^9+7取模。
题解
和bzoj101x的那道线段树维护区间连通性很像,每个节点维护4个值,从左到左,从左到右,从右到左,从右到右的方案数。区间合并的时候通过这几个转移一下就行。单点修改,区间查询,时间复杂度O(nlogn)。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 50005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
#define mod 1000000007
int n,m;
struct node{
    ll x[4];
}a[N<<2],ans;
void update(node &a,node b,node c)
{
    a.x[0]=b.x[0]*c.x[0]+b.x[2]*c.x[3];
    a.x[1]=b.x[1]*c.x[1]+b.x[3]*c.x[2];
    a.x[2]=b.x[0]*c.x[2]+b.x[2]*c.x[1];
    a.x[3]=b.x[3]*c.x[0]+b.x[1]*c.x[3];
    a.x[0]%=mod;a.x[1]%=mod;a.x[2]%=mod;a.x[3]%=mod;
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        a[rt].x[0]=a[rt].x[1]=a[rt].x[2]=a[rt].x[3]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    update(a[rt],a[rt<<1],a[rt<<1|1]);
}
void change(int l,int r,int rt,int pos,int x,int y)
{
    if(l==r)
    {
        if(x==1&&y==1) a[rt].x[0]^=1;
        else if(x==2&&y==2) a[rt].x[1]^=1;
        else if(x==1&&y==2) a[rt].x[2]^=1;
        else a[rt].x[3]^=1;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) change(lson,pos,x,y);
    else change(rson,pos,x,y);
    update(a[rt],a[rt<<1],a[rt<<1|1]);
}
node get_ans(int l,int r,int rt,int L,int R)
{
    if(L==l&&R==r) return a[rt];
    int mid=(l+r)>>1;
    if(R<=mid) return get_ans(lson,L,R);
    else if(L>mid) return get_ans(rson,L,R);
    else 
    {
        node tmp;
        update(tmp,get_ans(lson,L,mid),get_ans(rson,mid+1,R));
        return tmp;
    }
}
int main()
{
    while(cin>>n>>m)
    {
        n--;
        build(1,n,1);
        for(int op,x,y,z,i=1;i<=m;i++)
        {
            scanf("%d",&op);
            if(op==0)
            {
                scanf("%d%d",&x,&y);y--;
                ans=get_ans(1,n,1,x,y);
                printf("%I64d\n",(ans.x[0]+ans.x[1]+ans.x[2]+ans.x[3])%mod);
            }
            else
            {
                scanf("%d%d%d",&x,&y,&z);
                change(1,n,1,x,y,z);
            }
        }
    }
    return 0;
}```