Description：

给一个序列，支持区间按位与，区间求和，区间随机选两个数(可以相同)和的平方的期望 $\times(r-l+1)^2$ 。

$1\leqslant n\leqslant 10^5$

Solution：

第一个操作可以直接暴力做，因为有意义的与操作一定会消掉某个二进制位，所以一个数的操作次数不超过 $\log_2n​$ 次，第三个操作发现实际要求的就是： $$ \begin{align} &=\sum_{i=l}^r\sum_{j=l}^r(a[i]+a[j])^2\\ &=\sum_{i=l}^r\sum_{j=l}^r(a[i]^2+2a[i]a[j]+a[j]^2)\\ &=\sum_{i=l}^ra[i]^2\times (r-l+1)+2\sum_{i=l}^r\sum_{j=l}^ra[i]a[j]+\sum_{j=l}^ra[j]^2\times(r-l+1)\\ &=2\left((r-l+1)\sum_{i=l}^ra[i]^2+(\sum_{i=l}^ra[i])^2\right) \end{align} $$

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,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,q;

#define MAXN 100010

#define MOD 998244353

int a[MAXN];

typedef long long ll;

struct node

{

	int lc,rc;

	ll orsum;

	ll sum,sqrsum;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

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

{

	rt = newnode();

	if(l == r)

	{

		t[rt].orsum = a[l];

		t[rt].sum = a[l];

		t[rt].sqrsum = 1ll * a[l] * a[l] % MOD;

		return;

	}

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

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

	t[rt].orsum = t[t[rt].lc].orsum | t[t[rt].rc].orsum;

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	t[rt].sqrsum = (t[t[rt].lc].sqrsum + t[t[rt].rc].sqrsum) % MOD;

	return;

}

void change(int rt,int L,int R,int k,int l,int r)

{

	if((t[rt].orsum | k) == k)return;

	if(l == r)

	{

		t[rt].orsum &= k;

		t[rt].sum = t[rt].orsum;

		t[rt].sqrsum = t[rt].sum * t[rt].sum % MOD;

		return;

	}

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

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

	t[rt].orsum = t[t[rt].lc].orsum | t[t[rt].rc].orsum;

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	t[rt].sqrsum = (t[t[rt].lc].sqrsum + t[t[rt].rc].sqrsum) % MOD;

	return;

}

ll calcsum(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sum;

	ll res = 0;

	if(L <= mid)res += calcsum(t[rt].lc,L,R,l,mid);

	if(R > mid)res += calcsum(t[rt].rc,L,R,mid + 1,r);

	return res;

}

ll calcsqr(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sqrsum;

	ll res = 0;

	if(L <= mid)res = (res + calcsqr(t[rt].lc,L,R,l,mid)) % MOD;

	if(R > mid)res = (res + calcsqr(t[rt].rc,L,R,mid + 1,r)) % MOD;

	return res;

}

int main()

{

	freopen("seg.in","r",stdin);

	freopen("seg.out","w",stdout);

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)a[i] = rd();

	build(root,1,n);

	scanf("%d",&q);

	int opt,l,r,x;

	for(register int i = 1;i <= q;++i)

	{

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

		if(opt == 1)

		{

			x = rd();

			change(root,l,r,x,1,n);

		}

		if(opt == 2)

		{

			printf("%lld\n",calcsum(root,l,r,1,n));

		}

		if(opt == 3)

		{

			ll sqrs = calcsqr(root,l,r,1,n),s = calcsum(root,l,r,1,n) % MOD;

			ll ans = (sqrs * (r - l + 1) % MOD + s * s % MOD) % MOD * 2 % MOD;

			printf("%lld\n",ans);

		}

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}