http://uoj.ac/problem/291 (题目链接)
题意
一个写错的树状数组有多大的概率与正常树状数组得出的答案一样。
Solution
可以发现这个树状数组维护的是后缀和。
所以二维线段树维护二维数点$(l,r)$，表示左端点$l$与右端点$r$被修改次数相等的几率有多大。
对于$l=1$的情况，另外开一个普通的线段树维护，操作不用重写。
细节
标记可持久化，不然好像会被hack数据卡TLE？
代码
// uoj291
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf (1ll<<29)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std; const int maxn=100010,MOD=998244353;
int n,m,rt[maxn<<2],ans;
struct node {
int son[2],p;
int& operator [] (int x) {return son[x];}
}tr[maxn*400]; LL power(LL a,LL b) {
LL res=1;
while (b) {
if (b&1) (res*=a)%=MOD;
b>>=1;(a*=a)%=MOD;
}
return res;
} namespace D2 {
int sz;
void modify(int &k,int l,int r,int s,int t,int p) {
if (!k) k=++sz,tr[k].p=1;
if (s<=l && r<=t) {
tr[k].p=(1LL*tr[k].p*p%MOD+1LL*(1-tr[k].p+MOD)*(1-p+MOD)%MOD)%MOD;
return;
}
int mid=(l+r)>>1;
if (s<=mid) modify(tr[k][0],l,mid,s,t,p);
if (t>mid) modify(tr[k][1],mid+1,r,s,t,p);
}
void query(int k,int l,int r,int p) {
if (!k) return;
ans=(1LL*ans*tr[k].p%MOD+1LL*(1-ans+MOD)*(1-tr[k].p+MOD)%MOD)%MOD;
int mid=(l+r)>>1;
if (p<=mid) query(tr[k][0],l,mid,p);
else query(tr[k][1],mid+1,r,p);
}
} namespace D1 {
void modify(int k,int l,int r,int s1,int t1,int s2,int t2,int p) {
if (s1<=l && r<=t1) {
D2::modify(rt[k],1,n,s2,t2,p);
return;
}
int mid=(l+r)>>1;
if (s1<=mid) modify(k<<1,l,mid,s1,t1,s2,t2,p);
if (t1>mid) modify(k<<1|1,mid+1,r,s1,t1,s2,t2,p);
}
void query(int k,int l,int r,int s,int t) {
D2::query(rt[k],1,n,t);
if (l==r) return;
int mid=(l+r)>>1;
if (s<=mid) query(k<<1,l,mid,s,t);
else query(k<<1|1,mid+1,r,s,t);
}
} int main() {
scanf("%d%d",&n,&m);
for (int op,l,r,i=1;i<=m;i++) {
scanf("%d%d%d",&op,&l,&r);
if (op==1) {
int p=power(r-l+1,MOD-2);
if (l!=r) D1::modify(1,1,n,l,r,l,r,(1-2*p%MOD+MOD)%MOD);
if (l>1) {
D1::modify(1,1,n,1,l-1,l,r,(1-p+MOD)%MOD);
D2::modify(rt[0],1,n,1,l-1,0);
}
if (r<n) {
D1::modify(1,1,n,l,r,r+1,n,(1-p+MOD)%MOD);
D2::modify(rt[0],1,n,r+1,n,0);
}
D2::modify(rt[0],1,n,l,r,p);
}
if (op==2) {
--l;ans=1;
if (!l) D2::query(rt[0],1,n,r);
else D1::query(1,1,n,l,r);
printf("%d\n",ans);
}
}
return 0;
}