uoj#291 【ZJOI2017】树状数组

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <complex>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cstdio>
  8 #include <vector>
  9 #include <cmath>
 10 #include <queue>
 11 #include <stack>
 12 #include <map>
 13 #include <set>
 14 #define rhl (998244353)
 15 #define lson (x<<1)
 16 #define rson (x<<1|1)
 17 #define mid ((l+r)>>1)
 18 #define inf (1<<30)
 19 #define N (100010)
 20 #define il inline
 21 #define RG register
 22 #define ll long long
 23 #define merge(p1,p2) ( (p1*p2+(1-p1+rhl)*(1-p2+rhl))%rhl ) //合并操作
 24 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 25 
 26 using namespace std;
 27 
 28 int ls[330*N],rs[330*N],rt[4*N],sz; //二维线段树
 29 ll sum[330*N],ans;
 30 int n,m;
 31 
 32 il int gi(){
 33     RG int x=0,q=1; RG char ch=getchar();
 34     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();
 35     if (ch==‘-‘) q=-1,ch=getchar();
 36     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();
 37     return q*x;
 38 }
 39 
 40 //求逆元
 41 il ll qpow(RG ll a,RG ll b){
 42     RG ll ans=1;
 43     while (b){
 44     if (b&1) ans=ans*a;
 45     a=a*a,b>>=1;
 46     if (ans>=rhl) ans%=rhl;
 47     if (a>=rhl) a%=rhl;
 48     }
 49     return ans;
 50 }
 51 
 52 //内层线段树修改
 53 il void update(RG int &x,RG int l,RG int r,RG int xl,RG int xr,RG ll v){
 54     if (!x) sum[x=++sz]=1;
 55     if (xl<=l && r<=xr){
 56     sum[x]=merge(sum[x],v);
 57     return;
 58     }
 59     if (xr<=mid) update(ls[x],l,mid,xl,xr,v);
 60     else if (xl>mid) update(rs[x],mid+1,r,xl,xr,v);
 61     else update(ls[x],l,mid,xl,mid,v),update(rs[x],mid+1,r,mid+1,xr,v);
 62     return;
 63 }
 64 
 65 //内层线段树查询
 66 il void query(RG int x,RG int l,RG int r,RG int p){
 67     if (!x) return; ans=merge(ans,sum[x]); if (l==r) return;
 68     p<=mid?query(ls[x],l,mid,p):query(rs[x],mid+1,r,p); return;
 69 }
 70 
 71 //外层线段树修改
 72 il void Update(RG int x,RG int l,RG int r,RG int l1,RG int r1,RG int l2,RG int r2,RG ll v){
 73     if (l1<=l && r<=r1){ update(rt[x],0,n+1,l2,r2,v); return; }
 74     if (r1<=mid) Update(lson,l,mid,l1,r1,l2,r2,v);
 75     else if (l1>mid) Update(rson,mid+1,r,l1,r1,l2,r2,v);
 76     else Update(lson,l,mid,l1,mid,l2,r2,v),Update(rson,mid+1,r,mid+1,r1,l2,r2,v);
 77     return;
 78 }
 79 
 80 //外层线段树查询
 81 il void Query(RG int x,RG int l,RG int r,RG int p1,RG int p2){
 82     if (rt[x]) query(rt[x],0,n+1,p2); if (l==r) return;
 83     p1<=mid?Query(lson,l,mid,p1,p2):Query(rson,mid+1,r,p1,p2);
 84     return;
 85 }
 86 
 87 il void work(){
 88     n=gi(),m=gi(); RG int type,l,r;
 89     for (RG int i=1;i<=m;++i){
 90     type=gi(),l=gi(),r=gi();
 91     if (type==1){
 92         RG ll p=qpow(r-l+1,rhl-2);
 93         //一个点被修改的概率为p=1/(r-l+1)
 94         //l!=1的情况
 95         if (l>1) Update(1,0,n,1,l-1,l,r,(1-p+rhl)%rhl);
 96         if (r<n) Update(1,0,n,l,r,r+1,n,(1-p+rhl)%rhl);
 97         //[1,l-1]与[l,r]和[l,r]与[r+1,n]之间,修改次数相等的概率为(1-p)
 98         RG ll pp=p<<1; if (pp>=rhl) pp-=rhl;
 99         Update(1,0,n,l,r,l,r,(1-pp+rhl)%rhl);
100         //[l+r]与[l+r]之间,修改次数相等的概率为1-2*p
101         //l==1的情况
102         Update(1,0,n,0,0,0,l-1,0);
103         Update(1,0,n,0,0,r+1,n+1,0);
104         //[0,l-1]和[r+1,n+1]这两个区间,前缀和等于后缀和的概率为0
105         Update(1,0,n,0,0,l,r,p);
106         //[l,r]这个区间,前缀和等于后缀和的概率为p
107     } else{
108         ans=1,Query(1,0,n,l-1,r);
109         //查询操作,即查询(l-1,r)修改次数相等的概率
110         //若l==1,即查询r的前缀和等于后缀和的概率
111         printf("%lld\n",ans);
112     }
113     }
114     return;
115 }
116 
117 int main(){
118     File("bit");
119     work();
120     return 0;
121 }