【ZJOI2017】树状数组 题解

题目大意

  有一个错误的树状数组，它的修改往前走，询问往后走（find(0) 的时候返回 0）。
  现在有一个初始全 0 的序列，有两种操作：
  1 x y：在区间 [ x, y ] 中等概率随机一个 i，然后 a[i]=(a[i]+1)%2
  2 x y：询问 ( a[x]+…+a[y] )%2
  求这个错误树状数组对于每个询问回答正确的概率。
  n, m<=1e5

题解

  这个题的询问时的 x=1 的话要特殊考虑。

询问 x>1

  这个树状数组在 find(x) 的时候返回的是从 x 开始的后缀和。
  （可以打表发现，也可以从 change(y) 对 find(x) 的影响来证明，证明就是根据 y 和 x 的大小关系分别讨论。）

  因此询问 x 到 y，就是询问 ( a[x-1]+…+a[y-1] )%2
  因此回答错误当且仅当 x-1 的修改次数模 2 意义下不等于 y 的修改次数（即和为奇数）。

  所以把询问看作点 (x-1, y)，我们用树套树来维护这个平面。第一棵树表示第一维坐标，第二棵树表示第二维坐标。
  对于修改操作 (x, y)，它会对三种询问点产生影响：若询问点只包含 x 或只包含 y，那么有 1/(y-x+1) 的几率反色；若两个都包含，则 2/(y-x+1) 的几率反色。

  若当前为 0 的概率是 x，然后有 p 的几率反色，则 x 变成 x(1-p)+(1-x)p。此式也适用于标记合并。

询问 x=1

  这时候相当于询问前缀和是否等于后缀和。依然用上面的思想维护。

代码

#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=1e5+5, maxtr=4e7+5;
const LL mo=998244353;

int n,m;

LL mul(LL x,LL y) //这里为了卡常写得有点丑
{
	LL t=(1-2*y)%mo; t=(t<0) ?t+mo :t ;
	t=t*x+y; t=(t>=mo) ?t%mo :t ;
	return t;
}

int son[maxtr][2],bz[maxtr],root[4*maxn],sum;
LL ans;
void xg_sec(int &k,int l,int r,int x,int y,LL z)
{
	if (!k) bz[ k=++sum ]=0;
	if (l==x && r==y)
	{
		bz[k]=mul(bz[k],z);
		return;
	}
	int t1=(l+r)>>1;
	if (y<=t1) xg_sec(son[k][0],l,t1,x,y,z);
		else if (x>t1) xg_sec(son[k][1],t1+1,r,x,y,z);
			else xg_sec(son[k][0],l,t1,x,t1,z), xg_sec(son[k][1],t1+1,r,t1+1,y,z);
}
void xg_fir(int k,int l,int r,int x1,int y1,int x2,int y2,LL z)
{
	if (l==x1 && r==y1)
	{
		xg_sec(root[k],0,n,x2,y2,z);
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	if (y1<=t1) xg_fir(t,l,t1,x1,y1,x2,y2,z);
		else if (x1>t1) xg_fir(t+1,t1+1,r,x1,y1,x2,y2,z);
			else xg_fir(t,l,t1,x1,t1,x2,y2,z), xg_fir(t+1,t1+1,r,t1+1,y1,x2,y2,z);
}
void cx_sec(int k,int l,int r,int x)
{
	while (l<r)
	{
		if (!k) return;
		ans=mul(ans,bz[k]);
		int t1=(l+r)>>1;
		if (x<=t1) k=son[k][0], r=t1;
			else k=son[k][1], l=t1+1;
	}
	if (k) ans=mul(ans,bz[k]);
}
void cx_fir(int k,int l,int r,int x,int y)
{
	while (l<r)
	{
		if (root[k]) cx_sec(root[k],0,n,y);
		int t=k<<1, t1=(l+r)>>1;
		if (x<=t1) k=t, r=t1;
			else k=t+1, l=t1+1;
	}
	if (root[k]) cx_sec(root[k],0,n,y);
}

LL mi(LL x,LL y)
{
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

int main()
{
	scanf("%d %d",&n,&m);
	while (m--)
	{
		int ty,x,y;
		scanf("%d %d %d",&ty,&x,&y);
		if (ty==1)
		{
			LL p=mi(y-x+1,mo-2);
			if (1<=x-1) xg_fir(1,0,n,1,x-1,x,y,p);
			if (y+1<=n) xg_fir(1,0,n,x,y,y+1,n,p);
			xg_fir(1,0,n,x,y,x,y,p*2%mo);
			
			xg_fir(1,0,n,0,0,0,x-1,1);
			if (y+1<=n) xg_fir(1,0,n,0,0,y+1,n,1);
			xg_fir(1,0,n,0,0,x,y,p*(y-x)%mo);
		} else
		{
			ans=1;
			cx_fir(1,0,n,x-1,y);
			
			printf("%lld\n",ans);
		}
	}
}