【BZOJ4785】[Zjoi2017]树状数组

 漆黑的晚上，九条可怜躺在床上辗转反侧。难以入眠的她想起了若干年前她的一次悲惨的OI 比赛经历。那是一道基础的树状数组题。给出一个长度为 n 的数组 A，初始值都为 0，接下来进行 m 次操作，操作有两种：

#include <cstdio>#include <cstring>#include <iostream>#define z(_) (((_)%mod+mod)%mod)#define lson x<<1#define rson x<<1|1using namespace std;typedef long long ll;const ll mod=998244353;const int maxn=100010;int n,m,tot;ll inv(ll x){	ll z=1,y=mod-2;	while(y)	{		if(y&1)	z=z*x%mod;		x=x*x%mod,y>>=1;	}	return z;}ll calc(ll a,ll b){	return z(a*b+(1-a)*(1-b));}int rd(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}int ls[maxn<<8],rs[maxn<<8],rt[maxn<<2];ll s[maxn<<8];void up1(int l,int r,int &x,int a,int b,ll c){	if(!x)	x=++tot,s[x]=1;	if(a<=l&&r<=b)	{		s[x]=calc(s[x],c);		return ;	}	int mid=l+r>>1;	if(a<=mid)	up1(l,mid,ls[x],a,b,c);	if(b>mid)	up1(mid+1,r,rs[x],a,b,c);}ll q1(int l,int r,int x,int a){	if(!x)	return 1;	if(l==r)	return s[x];	int mid=l+r>>1;	if(a<=mid)	return calc(s[x],q1(l,mid,ls[x],a));	else	return calc(s[x],q1(mid+1,r,rs[x],a));}void up2(int l,int r,int x,int a,int b,int c,int d,ll e){	if(a<=l&&r<=b)	{		up1(1,n,rt[x],c,d,e);		return ;	}	int mid=l+r>>1;	if(a<=mid)	up2(l,mid,lson,a,b,c,d,e);	if(b>mid)	up2(mid+1,r,rson,a,b,c,d,e);}ll q2(int l,int r,int x,int a,int b){	if(l==r)	return q1(1,n,rt[x],b);	int mid=l+r>>1;	if(a<=mid)	return calc(q1(1,n,rt[x],b),q2(l,mid,lson,a,b));	else	return calc(q1(1,n,rt[x],b),q2(mid+1,r,rson,a,b));}int main(){	n=rd(),m=rd();	int i,a,b,c;	ll p,q;	for(i=1;i<=m;i++)	{		c=rd(),a=rd(),b=rd();		if(c==1)		{			p=inv(b-a+1);			if(a>1)	up2(0,n,1,1,a-1,a,b,z(1-p)),up2(0,n,1,0,0,0,a-1,0);			if(b<n)	up2(0,n,1,a,b,b+1,n,z(1-p)),up2(0,n,1,0,0,b+1,n,0);			up2(0,n,1,a,b,a,b,z(1-2*p)),up2(0,n,1,0,0,a,b,p);		}		else	printf("%lld\n",q2(0,n,1,a-1,b));	}	return 0;}