Description：

给出一个求后缀和但是按照求前缀和的方式相减的求区间异或和的树状数组，每次在一个区间内随机选一个异或，求询问一个区间得到正确结果的概率。

$1\leqslant n\leqslant 10^5$

Solution：

首先观察一下发现这样错的结果求出的答案实际上是 $ans\text{ xor }a[l-1]\text{ xor }a[r]$ ，也就是说如果 $a[l-1]=a[r]$ 的话就可以得到正确的结果。然后一个错误的思路是用线段树维护每个点被修改的概率，然而这样并不能维护，因为不能计算为什么我也不知道，但是可以用二维数据结构维护， $(x,y)$ 表示 $a[x]=a[y]$ 的概率，那么分情况讨论，假如当前修改的区间是 $[l,r]$ ：

1、 $x\in[l,r],y\notin[l,r]$ 或者 $x\notin[l,r],y\in[l,r]$ ，有 $\frac 1 {len}$ 的概率取反。

2、 $x,y\in[l,r]$ ，有 $\frac 2{len}$ 的概率取反，这个是因为不可能把 $x$ 和 $y$ 同时取反，那取反任意一个的概率显然是 $\frac 2{len}$ 。

然后这两种都可以分解为矩形修改问题，最后是单点查询，因此可以用标记永久化，就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res;

}

#define MOD 998244353

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int inv(int k){return power(k,MOD - 2);}

int n,m;

#define MAXN 100010

struct node

{

	int lc,rc;

	int val;

}t[MAXN << 8];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

int merge(int a,int b){return (1ll * a * (1 - b + MOD) % MOD + 1ll * b * (1 - a + MOD) % MOD) % MOD;}

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	int mid = ((l + r) >> 1);

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int &rt,int L,int R,int v,int l,int r)

{

	if(L > R)return;

	if(rt == 0)rt = newnode();

	if(L <= l && r <= R){t[rt].val = merge(t[rt].val,v);return;}

	int mid = ((l + r) >> 1);

	if(L <= mid)add(t[rt].lc,L,R,v,l,mid);

	if(R > mid)add(t[rt].rc,L,R,v,mid + 1,r);

	return;

}

int query(int rt,int p,int l,int r)

{

	if(rt == 0)return 0;

	if(l == r)return t[rt].val;int mid = ((l + r) >> 1);

	if(p <= mid)return merge(t[rt].val,query(t[rt].lc,p,l,mid));

	else return merge(t[rt].val,query(t[rt].rc,p,mid + 1,r));

}

void add(int rt,int L1,int R1,int L2,int R2,int v,int l,int r)

{

	if(L1 > R1 || L2 > R2)return;

	if(L1 <= l && r <= R1){add(t[rt].val,L2,R2,v,1,n);return;}

	int mid = ((l + r) >> 1);

	if(L1 <= mid)add(t[rt].lc,L1,R1,L2,R2,v,l,mid);

	if(R1 > mid)add(t[rt].rc,L1,R1,L2,R2,v,mid + 1,r);

	return;

}

int query(int rt,int x,int y,int l,int r)

{

	if(l == r)return query(t[rt].val,y,1,n);int mid = ((l + r) >> 1);

	if(x <= mid)return merge(query(t[rt].val,y,1,n),query(t[rt].lc,x,y,l,mid));

	else return merge(query(t[rt].val,y,1,n),query(t[rt].rc,x,y,mid + 1,r));

}

int root2;

int main()

{freopen("bit.in","r",stdin);

	n = rd();m = rd();

	build(root,1,n);

	int opt,l,r;

	for(int i = 1;i <= m;++i)

	{

		opt = rd();l = rd();r = rd();

		if(opt == 1)

		{

			int len = r - l + 1;

			add(root,l,r,r + 1,n,inv(len),1,n);

			add(root,1,l - 1,l,r,inv(len),1,n);

			add(root,l,r,l,r,2 * inv(len) % MOD,1,n);

			add(root2,1,l - 1,1,1,n);

			add(root2,r + 1,n,1,1,n);

			add(root2,l,r,(1 - inv(len) + MOD) % MOD,1,n);

		}

		else

		{

			if(l == 1)printf("%d\n",(1 - query(root2,r,1,n) + MOD) % MOD);

			else printf("%d\n",(1 - query(root,l - 1,r,1,n) + MOD) % MOD);

		}

	}

	return 0;

}