2020CCPC线段树 J

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#pragma GCC optimize(3,"Ofast","inline")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//typedef __int128 LL;//2的128
typedef long long ll; //2的64
// 1e9,, 1e19,,1e38
//#define int long long
typedef long long ll;
int n,m;
const int mod=998244353 ;
const int N=300010;
ll a[300010];
struct node{
int l,r,x[25];
ll sum;
};
node tr[N*4];
void pushup(int u){
    tr[u].sum=(tr[u*2].sum+tr[u*2+1].sum)%mod;
for(int i=0;i<25;i++)
    {
    tr[u].x[i] = tr[u*2].x[i] + tr[u*2+1].x[i];
    }
}
void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r){
        tr[u].sum=a[l]*a[l]%mod;
for(int i=0;i<25;++i)
        {
    tr[u].x[i] = a[l] >> i & 1;
        }
        return;
    }
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);  
}

void modify(int u,int l,int r,int s){
if(tr[u].l == tr[u].r) //就一个数的时候
    {
        ll sum = 0;
        for(int i=0;i<25;i++)
        {
            if(tr[u].x[i] && (s>>i&1)) 
            sum |= 1 << i; 

            else tr[u].x[i] = 0; 
        }
        tr[u].sum = sum * sum % mod;
    }
    if(tr[u].l>=l&&tr[u].r<=r){
    bool f = true;  
    for(int i=0;i<25;++i)
        //本身0   对面 1  不需要改
        //0   0        不需要
        //1     1  不需要      
        //1     0   需要改
        //不需要就return 需要就继续搜         
        if(tr[u].x[i] && (s>>i&1)==0)
            {
            f = false;  
                break;
            }
        if(f) return;  
    }
    int mid=(tr[u].l+tr[u].r)/2;
    if(l<=mid) modify(u*2,l,r,s);
    if(r>mid) modify(u*2+1,l,r,s);
    pushup(u);
}
ll query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].sum;
    }

     int mid=(tr[u].l+tr[u].r)/2;
    ll sum=0;
    if(l<=mid) sum=query(u*2,l,r)%mod;
    if(r>mid) sum=(sum+query(u*2+1,l,r))%mod;

    return sum;
}
void solve()
{   
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    cin>>m;
    while(m--){
        int ok=0;cin>>ok;
    if(ok==2){
        int z,y;cin>>z>>y;
        cout<<query(1,z,y)<<endl;
    }
    else{ int z,y,s; cin>>z>>y>>s;
    modify(1,z,y,s);
}

    }
}

signed main()
{
    ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

    solve();



    return 0;
}