BZOJ 4785 [Zjoi2017] 树状数组

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4785

题意：一个人的树状数组写错了，具体错在将修改操作和查询操作跳 lowbit 的顺序写反了，支持区间内随机单点取反，区间异或和查询，询问这个人的答案没错的概率。

如果熟悉树状数组或者打一下表可以简单的发现这个人写错的后果就是查询是后缀和不是前缀和了。

那么他的答案会错当且仅当 l-1 和 r 这两个位置被修改的次数在模 2 的意义下不同。将平面上的点 (l,r) 视作序列上的 l 和 r 这两个位置修改次数在模 2 意义下相同的概率。

每次修改操作分类讨论即可，实际上是三个矩形覆盖。概率可以简单合并，即分别讨论都变和都不变的情况即可，所以二维线段树可以维护这个修改。

如果只观察到这里就死定了，树状数组如果访问了 0 下标会炸，所以观察伪代码，发现访问 0 下标的时候返回了 0，不可以简单套用上述做法，单独维护下就好了。

二维线段树的话外层只需要维护上传标记即可，为了方便内层也写了标记永久化，其实没有必要。

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100010
#define ll long long
#define mod 998244353
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll quickmod(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1)ret=ret*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ret;
}
ll merge(ll a,ll b)
{return (a*b%mod+(1-a+mod)*(1-b+mod)%mod)%mod;}
ll p[N<<8];
int ch[N<<8][2],tot;
int root[N<<2];
int n,m;
struct ins_seg
{
    void modify(int &x,int l,int r,int L,int R,ll v)
    {
        if(!x)x=++tot,p[x]=1;
        if(l>=L&&r<=R)
        {
            p[x]=merge(p[x],v);
            return ;
        }
        int mid=(l+r)>>1;
        if(L<=mid) modify(ch[x][0],l,mid,L,R,v);
        if(R>mid)  modify(ch[x][1],mid+1,r,L,R,v);
    }

    ll ask(int x,int l,int r,int pos)
    {
        if(!x)return 1;
        if(l==r)return p[x];
        int mid=(l+r)>>1;

        if(pos<=mid)return merge(p[x],ask(ch[x][0],l,mid,pos));
        else return merge(p[x],ask(ch[x][1],mid+1,r,pos));
    }
};
struct out_seg
{
    ins_seg p;

    void modify(int x,int l,int r,int L,int R,int c,int d,ll v)
    {
        if(l>=L&&r<=R)
        {
            p.modify(root[x],1,n,c,d,v);
            return ;
        }
        int mid=(l+r)>>1;
        if(L<=mid) modify(x<<1,l,mid,L,R,c,d,v);
        if(R>mid)  modify(x<<1|1,mid+1,r,L,R,c,d,v);
    }

    ll ask(int x,int l,int r,int a,int b)
    {
        if(l==r)return p.ask(root[x],1,n,b);
        int mid=(l+r)>>1;
        if(a<=mid) return merge(p.ask(root[x],1,n,b),ask(x<<1,l,mid,a,b));
        else return merge(p.ask(root[x],1,n,b),ask(x<<1|1,mid+1,r,a,b));
    }
}T;

int main()
{
    n=read(),m=read();
    while(m--)
    {
        int opt=read(),l=read(),r=read();
        if(opt==1)
        {
            ll p=quickmod(r-l+1,mod-2);
            if(l>1) T.modify(1,0,n,1,l-1,l,r,(1-p+mod)%mod),T.modify(1,0,n,0,0,0,l-1,0);
            if(r<n) T.modify(1,0,n,l,r,r+1,n,(1-p+mod)%mod),T.modify(1,0,n,0,0,r+1,n,0);
            T.modify(1,0,n,l,r,l,r,(1-2*p%mod+mod)%mod);
            T.modify(1,0,n,0,0,l,r,p);
        }
        else printf("%lld\n",T.ask(1,0,n,l-1,r));
    }
}

100

101

102

103

104

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 100010

#define ll long long

#define mod 998244353

using namespace std;

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll quickmod(ll a,ll b)

{

ll ret=1;

while(b)

{

if(b&1)ret=ret*a%mod;

a=a*a%mod,b>>=1;

}

return ret;

}

ll merge(ll a,ll b)

{return (a*b%mod+(1-a+mod)*(1-b+mod)%mod)%mod;}

ll p[N<<8];

int ch[N<<8][2],tot;

int root[N<<2];

int n,m;

struct ins_seg

{

void modify(int &x,int l,int r,int L,int R,ll v)

{

if(!x)x=++tot,p[x]=1;

if(l>=L&&r<=R)

{

p[x]=merge(p[x],v);

return ;

}

int mid=(l+r)>>1;

if(L<=mid) modify(ch[x][0],l,mid,L,R,v);

if(R>mid) modify(ch[x][1],mid+1,r,L,R,v);

}

ll ask(int x,int l,int r,int pos)

{

if(!x)return 1;

if(l==r)return p[x];

int mid=(l+r)>>1;

if(pos<=mid)return merge(p[x],ask(ch[x][0],l,mid,pos));

else return merge(p[x],ask(ch[x][1],mid+1,r,pos));

}

};

struct out_seg

{

ins_seg p;

void modify(int x,int l,int r,int L,int R,int c,int d,ll v)

{

if(l>=L&&r<=R)

{

p.modify(root[x],1,n,c,d,v);

return ;

}

int mid=(l+r)>>1;

if(L<=mid) modify(x<<1,l,mid,L,R,c,d,v);

if(R>mid) modify(x<<1|1,mid+1,r,L,R,c,d,v);

}

ll ask(int x,int l,int r,int a,int b)

{

if(l==r)return p.ask(root[x],1,n,b);

int mid=(l+r)>>1;

if(a<=mid) return merge(p.ask(root[x],1,n,b),ask(x<<1,l,mid,a,b));

else return merge(p.ask(root[x],1,n,b),ask(x<<1|1,mid+1,r,a,b));

}

}T;

int main()

{

n=read(),m=read();

while(m--)

{

int opt=read(),l=read(),r=read();

if(opt==1)

{

ll p=quickmod(r-l+1,mod-2);

if(l>1) T.modify(1,0,n,1,l-1,l,r,(1-p+mod)%mod),T.modify(1,0,n,0,0,0,l-1,0);

if(r<n) T.modify(1,0,n,l,r,r+1,n,(1-p+mod)%mod),T.modify(1,0,n,0,0,r+1,n,0);

T.modify(1,0,n,l,r,l,r,(1-2*p%mod+mod)%mod);

T.modify(1,0,n,0,0,l,r,p);

}

else printf("%lld\n",T.ask(1,0,n,l-1,r));

}

zgz233

zgz233

BZOJ 4785 [Zjoi2017] 树状数组

l1ll5

Comments | 3 条评论

yyc

yycc

everlasting