BZOJ4785 树状数组

题目传送门

solution

写错的树状数组其实就是求一个后缀和,设suml[i]为前缀和,sumr[i]为后缀和,则题目要求suml[r]-suml[l-1],然后我们来比较一下suml[r]-sum[l-1]和-(sumr[l-1]-sumr[r])(相反数在mod 2 意义下相等)发现他们相差的就是val[l-1]和val[r],然后要使他们相等就是说val[l-1]和val[r]要在mod 2意义下相等,当l=1时就是询问一个点的前缀和和后缀和是否相等。
然后将每个询问看成一个二维平面上的点,(l-1,r),用树套树来维护点合法的概率,用(l1,r1,l2,r2)表示左端点在l1,r1间,右端点在(l2,r2)间的所有区间,然后在(l,r)区间内改一个点会影响到(1,l-1,l,r),(l,r,r+1,n),(l,r,l,r),计算两个端点这一次修改都不修改的概率。当l=1时前缀和等于后缀和的概率就是这个点被改的概率,因为它前面或后面被改了就不相等了,一次只改一个数。然后合并这些概率就得到了这个点合法的概率,设以前的概率是p1,这一次的概率是p2,合并就是$(p1p2+(1-p1)(1-p2))$就是两次都相等或都不相等,然后一合并就都相等了。
所以说问题就变成了改一个矩阵中的概率,单点询问。然后就是树套树打标记。

#include<cstdio>
using namespace std;
const int mod=998244353;
int n,ans,num,sum[29000005],ls[29000005],rs[29000005],root[400005];
int pow(int a,int b){
    int ans=1;
    while (b){
        if (b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b=b>>1; 
    }
    return ans;
}
int merge(int X,int Y){
    long long x=X,y=Y;
    long long ans=1ll*x*y%mod+1ll*(1-x+mod)*(1-y+mod)%mod;
    ans%=mod;
    ans+=mod;
    ans%=mod;
    return (int)ans;
}
void change_exp(int &k,int l,int r,int x,int y,int exp){
    if (!k){
        k=++num;
        sum[k]=1;
    }
    if (r<x || l>y) return;
    if (l>=x && r<=y){
        sum[k]=merge(sum[k],exp);
        return;
    }
    int mid=(l+r)>>1;
    change_exp(ls[k],l,mid,x,y,exp);
    change_exp(rs[k],mid+1,r,x,y,exp);
}
void change(int k,int l,int r,int x,int y,int ll,int rr,int exp){
    if (r<x || l>y) return;
    if (l>=x && r<=y){
        change_exp(root[k],0,n,ll,rr,exp);
        return;
    }
    int mid=(l+r)>>1;
    change(k<<1,l,mid,x,y,ll,rr,exp);
    change(k<<1|1,mid+1,r,x,y,ll,rr,exp);
}
void query_exp(int k,int l,int r,int id){
    if (!k) return;
    ans=merge(ans,sum[k]);
    if (l==r) return;
    int mid=(l+r)>>1;
    if (id<=mid) query_exp(ls[k],l,mid,id);
    else query_exp(rs[k],mid+1,r,id);
}
int query(int x,int y){
    int l=0,r=n,T=1;
    ans=1;
    query_exp(root[T],0,n,y);
    while (l!=r){
        int mid=(l+r)>>1;
        if (x<=mid) {
            query_exp(root[T<<1],0,n,y);
            T=T<<1;
            r=mid;
        }
        else{
            query_exp(root[T<<1|1],0,n,y);
            T=T<<1|1;
            l=mid+1;
        }
    }
    return ans;
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    while (m--){
        int cas;
        scanf("%d",&cas);
        if (cas==1){
            int l,r;
            scanf("%d%d",&l,&r);
            int exp=pow(r-l+1,mod-2)%mod;
            if (l>1) change(1,0,n,1,l-1,l,r,(1-exp+mod)%mod);
            if (r<n) change(1,0,n,l,r,r+1,n,(1-exp+mod)%mod);
            change(1,0,n,l,r,l,r,(1-2ll*exp%mod+mod)%mod);
            change(1,0,n,0,0,0,l-1,0);
            change(1,0,n,0,0,r+1,n,0);
            change(1,0,n,0,0,l,r,exp);
        }
        else{
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",query(l-1,r));
        }
    }
    return 0;
}

4 thoughts on “BZOJ4785 树状数组”

  1. I and my pals were following the great suggestions from the website then unexpectedly I got a terrible suspicion I never thanked the web site owner for those tips. My people became as a consequence thrilled to learn them and now have in truth been having fun with those things. I appreciate you for turning out to be considerably kind as well as for making a choice on this sort of useful guides millions of individuals are really wanting to know about. Our sincere apologies for not expressing appreciation to earlier.

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注