# BZOJ4785 树状数组

### solution

#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.