网站建设存在风险,wordpress 评论邮箱改成电话,wordpress开发商,安徽工程造价信息网2023河南省赛组队训练赛#xff08;二#xff09; - Virtual Judge (vjudge.net)
请你维护一个长度为 n 的非负整数序列 a1, a2, ..., an#xff0c;支持以下两种操作#xff1a;
第一种操作会将序列 al, al 1, ..., ar 中的每个元素#xff0c;修改为各自和 x…2023河南省赛组队训练赛二 - Virtual Judge (vjudge.net)
请你维护一个长度为 n 的非负整数序列 a1, a2, ..., an支持以下两种操作
第一种操作会将序列 al, al 1, ..., ar 中的每个元素修改为各自和 x 的二进制与Bitwise binary AND的值其中 l, r, x 在每次操作时会给定第二种操作会询问序列 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 l r x表示将序列中编号在区间 [l, r] 的所有元素修改为和 x 二进制与操作后的值其中 1 ≤ l ≤ r ≤ n, 0 ≤ x 224第二种操作的格式为 2 l r表示询问序列中编号在区间 [l, r] 的所有元素的平方和模 998 244 353 的值其中 1 ≤ l ≤ r ≤ n。
数据保证至少有一个第二种操作即保证至少询问一次答案。
Output
每当遇到第二种操作时输出询问的答案。注意需要取模。
Sample 1
InputcopyOutputcopy 3
13 31 28
4
2 1 3
1 3 3 25
1 1 2 18
2 2 31914
900Sample 2
InputcopyOutputcopy 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 5346
162
178Sample 3
InputcopyOutputcopy 4
16777215 16777215 16777215 16777214
4
2 2 2
1 1 4 16777214
2 1 4
2 3 4981185168
795789897
897017125Note
二进制与Bitwise binary AND结果的第 i 个二进制位为 1当且仅当两个操作数的第 i 位都为 1。
题解:
关键在于如何把区间修改转化为单点修改,维护区间1的个数
注意不要用#define int long long 会被卡时间(以后线段树不要用)
具体细节会在代码中有详细注释
#includeiostream
#includealgorithm
#includestring
#includecstring
#includevector
#includemap
#includequeue
#includecstdio
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[rt1].sum tre[rt 1|1].sum)%mod;for(int i 0;i 25;i){tre[rt].x[i] tre[rt1].x[i] tre[rt1|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 i1);//建树时把每个点一个的个数统计好}return ;}tre[rt].l l;tre[rt].r r;int mid (l r) 1;build(rt1,l,mid);build(rt1|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 i1){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 i1) 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 ltre[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(rt1|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
