看到题发现很难,不过随便想想就很容易想到需要维护 $a_{l-1}\equiv a_r\ \rm{mod}\ 2$ 的概率,然后直接二维线段树,不过嘴巴正解还是不代表写得出来,唉写的时候思路明显不清晰,难受死了。


运行一下可怜的代码,你会发现她的树状数组求的是后缀和。

也就是说,对于可怜的 $find(r)-find(l-1)$ ,其实求的是 $((\sum_{i=r}^{n}a_i)\%2-(\sum_{i=l-1}^{n}a_i)\%2+2)\%2$ ,后面的抵消了,于是可怜求出的柿子其实就是 $(\sum_{i=l-1}^{r-1}a_i)\%2$ .

然后正确的树状数组求出来的结果为:$(\sum_{i=l}^{r}a_i)\%2$ .

显然两个柿子相等当且仅当 $a_{l-1}\equiv a_r\ \rm{mod}\ 2$ 。

开个二维线段树,$t_{i,j}$ 维护 c的概率即可。


具体维护细节:

每一次的一个修改操作 $l,r$ ,我们需要更新线段树(废话) 。

  • 对于 $i\in [l,r],j\in [l,r]$ 的点 $t_{i,j}$ 来说,如果要使 $a_{i}\equiv a_j\ \rm{mod}\ 2$ 成立,那么 $i,j$ 中的任意一个都不能被修改,也就是说有 $1-\frac{2}{r-l+1}$ 的概率使得 $i,j$ 不被修改,从而使得 $a_{i}\equiv a_j\ \rm{mod}\ 2$ 继续成立,将所有的 $t_{i,j}$ 乘上一个 $1-\frac{2}{r-l+1}$ 即可。
  • 对于 $i\in [l,r],j\notin [l,r]$ 和 $i\notin [i,j],j\in [i,j]$ 的点 $t_{i,j}$ 来说,如果需要让 $a_{i}\equiv a_j\ \rm{mod}\ 2$ 继续成立,那么不能选中 $i,j$ 中存在于 $l,r$ 之间的那个,这样的概率是 $1-\frac{1}{r-l+1}$ ,将所有的这样的点 $t_{i,j}$ 乘上一个 $1-\frac{1}{r-l+1}$ 即可。
  • 对于所有的 $i\notin [l,r],j\notin[l,r]$ ,此次操作对 $t_{i,j}$ 没有影响(又是废话)。

然后还需要注意的就是,可怜的代码在 $l=1$ 的时候询问 $sum(l-1)$ 的结果为 $0$ ,仔细看她的伪代码你会发现 x==0 的时候是直接 return 0 的。

这个时候可怜的代码变成了求 $(\sum_{i=r}^{n}a_i)\% 2$ ,正解为 $(\sum_{i=1}^{r}a_i)\%2$ ,这两个柿子唯一重叠的部分就是 $r$ 位置(下文称为 $x$ 位置),如果这两个柿子相等,那么对于当前的修改操作 $l,r$ ,分三种情况:

  • $x< l$ ,这说明这次操作无论如何都会给 $(\sum_{i=r}^{n}a_i)\% 2$ 造成贡献,从而使其改变,那么这样子就不相等了,这样的概率为 $1$ 。
  • $x > r$ 和上面一样,如论如何都会给 $(\sum_{i=1}^{r}a_i)\% 2$ 造成贡献从而使其不平衡,概率同样为 $1$ 。
  • $x\in[l,r]$ ,这样子的话,只有选中 $x$ 位置才能使两个柿子平衡,概率为 $1-\frac{1}{r-l+1}$ 。

Code

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define freopen(A) {freopen(A".in","r",stdin);freopen(A".out","w",stdout);}

const int N=1e5+2;
const ll mod=998244353;
int n,m;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int merge(int x,int y) {
    return (1ll*x*y%mod+1ll*(1ll-x+mod)*(1ll-y+mod)%mod)%mod;
}
int pow(int x,int y) {
    int res=1;
    for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
    return res;
}

struct _2D_Segment_Tree {
    #define mid ((l+r)>>1)
    int root[N<<8];
    struct Segment {
        int tot,lc[N<<8],rc[N<<8],val[N<<8  ];
        int query(int&x,int l,int r,int pos) {
            if(!x) return 1;
            if(l==r) return val[x];
            return merge(val[x],(pos<=mid)?query(lc[x],l,mid,pos):query(rc[x],mid+1,r,pos));
        }
        void change(int&x,int l,int r,int L,int R,int v) {
            if(r<L||R<l) return;
            if(!x) x=++tot,val[x]=1;
            if(L<=l&&r<=R) {val[x]=merge(val[x],v);return;}
            change(lc[x],l,mid,L,R,v),change(rc[x],mid+1,r,L,R,v);
        }
    }T;
    int query(int x,int l,int r,int L,int R) {
        if(l==r) return T.query(root[x],0,n,R);
        return merge(T.query(root[x],0,n,R),(L<=mid)?query(x<<1,l,mid,L,R):query(x<<1|1,mid+1,r,L,R));
    }
    void change(int x,int l,int r,int XL,int XR,int YL,int YR,int v) {
        if(r<XL||XR<l) return;
        if(XL<=l&&r<=XR) {T.change(root[x],0,n,YL,YR,v);return;}
        change(x<<1,l,mid,XL,XR,YL,YR,v),change(x<<1|1,mid+1,r,XL,XR,YL,YR,v);
    }
}T;

int main() {
    // freopen("2251");
    IN(n),IN(m);while(m--) {
        int op,l,r;IN(op),IN(l),IN(r);
        if(op==1) {
            int P=pow(r-l+1,mod-2);
            if(l>1) T.change(1,0,n,1,l-1,l,r,(1-P+mod)%mod),T.change(1,0,n,0,0,0,l-1,0);
            if(r<n) T.change(1,0,n,l,r,r+1,n,(1-P+mod)%mod),T.change(1,0,n,0,0,r+1,n,0);          
            T.change(1,0,n,l,r,l,r,(1-2*P%mod+mod)%mod);
            T.change(1,0,n,0,0,l,r,P);
        } else printf("%d\n",T.query(1,0,n,l-1,r));
    }
    return 0;
}
最后修改:2019 年 08 月 27 日 10 : 34 AM