Submission #1097968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097968		SulA	XORanges (eJOI19_xoranges)	C++17	12 / 100	899 ms	3152 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod = 1000000007;
const int N = 200005;
// blocks size 446 because even
ll a[N+2], dp[N+2];
//   odd  even
pair<int, int> sq[N+2][33];
void solve(){
int n, q;
cin>>n>>q;
ll cnt = 0;
ll sqrtn = 446;
for(int i = 1; i <= n; i++){
cin>>a[i];
for(int j = 0; j < 32; j++){
if(i % 2 == 0)sq[i/sqrtn][j].first += (((1 << j) & a[i]) >= 1);
else sq[i/sqrtn][j].second += (((1 << j) & a[i]) >= 1);
}
}
while(q--){
int type;
cin>>type;
if(type == 1){
// update;
int u, v;
cin>>u>>v;
for(int j = 0; j < 32; j++){
if(u % 2 == 0)sq[u/sqrtn][j].first -= (((1 << j) & a[u]) >= 1), sq[u/sqrtn][j].first += (((1 << j) & v) >= 1);
else sq[u/sqrtn][j].second -= (((1 << j) & a[u]) >= 1), sq[u/sqrtn][j].second += (((1 << j) & v) >= 1);
}
a[u] = v;
}
else{
int l, r;
cin>>l>>r;
ll tmp[33] = {};
ll ans = 0;
if((r - l + 1) % 2 == 0){
cout<<0<<'\n';
continue;
}
if(r - l + 1 < sqrtn){
// do loop
for(int i = l, k = 1; i <= r; i++, k++){
for(int j = 0; j < 32; j++){
tmp[j] += (((1 << j) & a[i]) >= 1) * (r - l + 1 - k + 1) * k;
}
}
for(int j = 0; j < 32; j++){
if(tmp[j] % 2 == 1)ans |= (1 << j);
}
cout<<ans<<'\n';
continue;
}
for(int i = l/sqrtn+1; i < r/sqrtn; i++){
for(int j = 0; j < 32; j++){
tmp[j] += sq[i][j].first;
}
}
for(int i = l; i < (l/sqrtn+1) * sqrtn; i++){
if(i % 2 == 1){
for(int j = 0; j < 32; j++){
tmp[j] += (((1 << j) & a[i]) >= 1);
}
}
}
for(int i = (r/sqrtn)*sqrtn; i <= r; i++){
if(i % 2 == 1){
for(int j = 0; j < 32; j++){
tmp[j] += (((1 << j) & a[i]) >= 1);
}
}
}
for(int j = 0; j < 32; j++){
if(tmp[j] % 2 == 1)ans |= (1 << j);
}
cout<<ans<<'\n';
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin>>tt;
while(tt--){
solve();
cout<<'\n';
}
}

Compilation message (stderr)

xoranges.cpp: In function 'void solve()':
xoranges.cpp:19:4: warning: unused variable 'cnt' [-Wunused-variable]
   19 | ll cnt = 0;
      |    ^~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25