over 3 years ago

QAQ线段树真是好厉害……两道题的共同特点是行数特别少,可以简单储存
<!--more-->

hdu5068

这道题比较简单。但是调了好久。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 200001
#define Mod 1000000007
#define LL long long 
using namespace std;
struct node
{
    bool f[2][2];
    int s[2][2];
    node(){memset(f,false,sizeof(f));memset(s,0,sizeof(s));}
    void clear(){memset(f,false,sizeof(f));memset(s,0,sizeof(s));}
} a[maxn];
int n,m,y,z;
inline int read()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
inline int mul(int x,int y)
{
    LL r=x*(LL)y%Mod;
    return (int)r;
}
inline node merge(node P,node Q,bool f[2][2])
{
    node r;int i,j,k,p;
    for (i=0;i<2;i++)
        for (j=0;j<2;j++) r.f[i][j]=f[i][j];
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            for (k=0;k<2;k++)
                for (p=0;p<2;p++)
                    if (f[i][j])
                        r.s[k][p]=(r.s[k][p]+mul(P.s[k][i],Q.s[j][p]))%Mod;
    return r;
}
inline void build(int now,int left,int right)
{int i,j;
    if (left==right)
    {
        a[now].f[0][0]=a[now].f[1][1]=1;
        a[now].s[0][0]=a[now].s[1][1]=1;
        a[now].f[0][1]=a[now].f[1][0]=0;
        a[now].s[0][1]=a[now].s[1][0]=0; 
        return;       
    }
    int mid=(left+right)>>1;
    build(now*2,left,mid);
    build(now*2+1,mid+1,right);
    for (i=0;i<=1;i++)
        for (j=0;j<=1;j++)
            a[now].f[i][j]=true;
    a[now]=merge(a[now*2],a[now*2+1],a[now].f);
}
inline node query(int now,int left,int right,int l,int r)
{
    if (l<=left&&right<=r)return a[now];
    int mid=(left+right)>>1;
    node t1,t2;
    if (mid+1<=r&&l<=mid)
    {
        t1=query(now*2,left,mid,l,r);
        t2=query(now*2+1,mid+1,right,l,r);
        return merge(t1,t2,a[now].f);
    } 
    else
    {
        if (l<=mid) return query(now*2,left,mid,l,r);
        if (mid+1<=r) return query(now*2+1,mid+1,right,l,r);
    }
}
inline void change(int now,int left,int right,int l)
{
    if (left==right)return;
    int mid=(left+right)>>1;
    if (l==mid)
    {
        a[now].f[y][z]=!a[now].f[y][z];
        a[now]=merge(a[now*2],a[now*2+1],a[now].f);
        return;
    }
    if (l<mid) change(now*2,left,mid,l);//!!!
     else change(now*2+1,mid+1,right,l);
    a[now]=merge(a[now*2],a[now*2+1],a[now].f);
}
int main()
{
    int i,j,x,k,o;node r;int sum=0;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,1,n);
        while (m--)
        {scanf("%d",&o);
            if (o==0)
            {
                scanf("%d%d",&x,&y);
                r=query(1,1,n,x,y);
                sum=0;
                for (i=0;i<2;i++)
                    for (j=0;j<2;j++)
                        sum=(sum+r.s[i][j])%Mod;
                printf("%d\n",sum);
            }
            else
            {
                scanf("%d%d%d",&x,&y,&z);y--;z--;
                change(1,1,n,x);
            }
        }
    } 
}

bzoj1018

这道题的重点在于左端点和右端点的连通性可能由于区间的增大而改变,就是绕了一圈连通的情况。
而且查询也存在绕了一圈的情况。
所以要考虑周全。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 400001
using namespace std;
struct link
{
    bool f[2][2],l,r;
    link(){memset(f,false,sizeof(f));l=r=false;}
};
struct node
{
    link st;bool l1,l2;
}a[maxn];
int r1,r2,c;bool ans;char s[10];
inline int read()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
inline void build(int now,int left,int right)
{
    if (left==right)
    {
        a[now].st.f[0][0]=a[now].st.f[1][1]=a[now].l1=a[now].l2=1;
        return;
    }
    int mid=(left+right)>>1;
    build(now*2,left,mid);
    build(now*2+1,mid+1,right);
}
inline link merge(link p,link q,bool l1,bool l2)
{
    link r;int i,j;
    r.l=p.l|(p.f[0][0]&&p.f[1][1]&&l1&&l2&&q.l);
    r.r=q.r|(q.f[0][0]&&l1&&l2&&p.r&&q.f[1][1]);
    if (l1)
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            r.f[i][j]|=p.f[i][0]&&q.f[0][j];
    if (l2)
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            r.f[i][j]|=p.f[i][1]&&q.f[1][j];
    return r;
}
inline void change(int now,int left,int right,int l,bool color)
{
    int mid=(left+right)>>1;
    if (r1==r2&&mid==l)
    {
        if (r1==0)   a[now].l1=color;
        else a[now].l2=color;
        a[now].st=merge(a[now*2].st,a[now*2+1].st,a[now].l1,a[now].l2);
        return;
    }
    if (left==right)
    {
        a[now].st.f[0][1]=a[now].st.f[1][0]=a[now].st.l=a[now].st.r=color;
        return;
    }
    if (l<=mid) change(now*2,left,mid,l,color);
    else change(now*2+1,mid+1,right,l,color);
    a[now].st=merge(a[now*2].st,a[now*2+1].st,a[now].l1,a[now].l2);
}
inline link query(int now,int left,int right,int l,int r)
{
    if (l<=left&&r>=right) return a[now].st;
    int mid=(left+right)>>1;link r1,r2;
    if (l<=mid&&r>mid)
    {
        r1=query(now*2,left,mid,l,r);
        r2=query(now*2+1,mid+1,right,l,r);
        return merge(r1,r2,a[now].l1,a[now].l2);
    }
    else
    {
        if (l<=mid) return query(now*2,left,mid,l,r);
        if (r>mid) return query(now*2+1,mid+1,right,l,r);
    }
}
int main()
{
    int i,j,k,c1,c2;link left,right,mid;
    c=read();
    build(1,1,c);
    while (scanf("%s",s))
    {
        if (strcmp(s,"Exit")==0) break;
        r1=read()-1;c1=read();r2=read()-1;c2=read();
        if (c1>c2) {int o=c1;c1=c2;c2=o;o=r1;r1=r2;r2=o;} 
        if (s[0]=='O') change(1,1,c,c1,true);
        if (s[0]=='C') change(1,1,c,c1,false); 
        if (s[0]=='A')
        {
            ans=false;
            left=query(1,1,c,1,c1);
            right=query(1,1,c,c2,c);
            mid=query(1,1,c,c1,c2);
            for (i=0;i<2;i++)
                for (j=0;j<2;j++)
                    if (mid.f[i][j])
                        if ((i==r1||left.r)&&(j==r2||right.l)) ans=true;
            if (ans) printf("Y\n");else printf("N\n");
        }
    }
}
← neerc southern 【bzoj1858】【线段树】序列操作 →
 
comments powered by Disqus