J - 二进制与、平方和(线段树 + 维护区间1的个数)

2023河南省赛组队训练赛（二） - Virtual Judge (vjudge.net)

请你维护一个长度为 n 的非负整数序列 a1, a2, ..., an，支持以下两种操作：

1. 第一种操作会将序列 al, al + 1, ..., ar 中的每个元素，修改为各自和 x 的"二进制与"（Bitwise binary AND）的值，其中 l, r, x 在每次操作时会给定；
2. 第二种操作会询问序列 al, al + 1, ..., ar 中所有元素的平方和模 998 244 353 的值，即 

   

    模 998 244 353，其中 l, r 在每次操作时会给定。

总共有 q 次操作，请你在维护序列的过程中，输出第二种操作所询问的答案。注意需要取模。

Input

第一行，一个整数 n (1 ≤ n ≤ 3 × 105)，表示序列的长度。

第二行，共 n 个整数 ai (0 ≤ ai < 224)，表示序列。

第三行，一个整数 q (1 ≤ q ≤ 3 × 105)，表示询问的数量。

接下来 q 行，每行表示一个操作，输入有两种格式：

1. 第一种操作的格式为 "1 l r x"，表示将序列中编号在区间 [l, r] 的所有元素，修改为和 x 二进制与操作后的值，其中 1 ≤ l ≤ r ≤ n, 0 ≤ x < 224；
2. 第二种操作的格式为 "2 l r"，表示询问序列中编号在区间 [l, r] 的所有元素的平方和，模 998 244 353 的值，其中 1 ≤ l ≤ r ≤ n。

数据保证至少有一个第二种操作，即保证至少询问一次答案。

Output

每当遇到第二种操作时，输出询问的答案。注意需要取模。

Sample 1

Inputcopy	Outputcopy
3 13 31 28 4 2 1 3 1 3 3 25 1 1 2 18 2 2 3	1914 900

Sample 2

Inputcopy	Outputcopy
5 9 11 12 5 1 7 2 1 3 1 3 3 0 1 1 3 9 1 4 5 13 2 1 3 1 4 5 14 2 1 5	346 162 178

Sample 3

Inputcopy	Outputcopy
4 16777215 16777215 16777215 16777214 4 2 2 2 1 1 4 16777214 2 1 4 2 3 4	981185168 795789897 897017125

Note

"二进制与"（Bitwise binary AND）结果的第 i 个二进制位为 1，当且仅当两个操作数的第 i 位都为 1。

题解:

关键在于如何把区间修改转化为单点修改,维护区间1的个数

注意不要用#define int long long 会被卡时间(以后线段树不要用)

具体细节会在代码中有详细注释 

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
using namespace std;
//#define int long long
const int N = 3e5 + 10; 
typedef long long ll;
int mod = 998244353;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
struct node
{int l,r,sum;int x[30];
}tre[N*4];
int w[N];
void pushup(int rt)
{tre[rt].sum = ((ll)tre[rt<<1].sum + tre[rt <<1|1].sum)%mod;for(int i = 0;i < 25;i++){tre[rt].x[i] = tre[rt<<1].x[i] + tre[rt<<1|1].x[i];//小区间的1的个数组成大区间1的个数}
}
void build(int rt,int l,int r)
{if(l == r){tre[rt].sum = (ll)w[l]*w[l]%mod;tre[rt].l = l;tre[rt].r = r;int x = w[l];for(int i = 0;i < 25;i++){tre[rt].x[i] = (x >> i&1);//建树时把每个点一个的个数统计好}return ;}tre[rt].l = l;tre[rt].r = r;int mid = (l + r) >> 1;build(rt<<1,l,mid);build(rt<<1|1,mid + 1,r);pushup(rt);
}
void updata(int rt,int l,int r,int x)
{if(tre[rt].l == tre[rt].r){int s = 0;for(int i = 0;i < 25;i++){if(tre[rt].x[i]&&x >> i&1){s |= 1 <<i;}else{tre[rt].x[i] = 0;}}//更新到某个具体时跟新每一位和x的&值tre[rt].sum = (ll)s*s%mod;return ;}if(tre[rt].l >= l && tre[rt].r <= r){bool f = 1;for(int i = 0;i < 25;i++){if(tre[rt].x[i] && (x >> i&1) ==0){f = 0;break;}}if(f)//此时区间是要求区间的一部分,符合条件不用继续向下找了return ;}int mid = tre[rt].l + tre[rt].r >> 1;if(l <= mid){updata(rt << 1,l,r,x);}if(r > mid){updata(rt << 1|1,l,r,x);}pushup(rt);}
int query(int rt,int l,int r)
{if(tre[rt].l >= l&&tre[rt].r <=r){return tre[rt].sum; }int mid = tre[rt].l + tre[rt].r >> 1;int s = 0;if(l <= mid)s = query(rt << 1,l,r);if(r> mid)s = ((ll)s + query(rt<<1|1,l,r))%mod;return s;
}
void solve()
{int m,n;scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &w[i]);build(1, 1, n);scanf("%d", &m);while (m--){int p,l, r, x;scanf("%d%d%d", &p, &l, &r);if (p == 1){scanf("%d", &x);updata(1, l, r, x);}else{printf("%d\n", query(1, l, r));}}
}
int main()
{
//	ios;int t = 1;
//	cin >> t;while(t--){solve();} 
}
//3 F
//5 B
//6 F
//9 F
//10 B
//12 F
//15 FB
//18 FB