#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & -(S))
/*
8 4
1 2 3 4 5 6 7 8
2 3 7
2 3 6
2 2 7
2 2 6
*/
/*
*/
//parece funcionar
void modificar(const int &v, vector<int> &a, const int &l, const int &r, const int &i, const int &j) {
// cout << "modificar l=" << l << ", r=" << r << endl;
if (l > j || r < j) return;
// cout << "\tmodificado" << endl;
a[i] ^= v;
if (l >= r) return;
// cout << "\tno es hoja" << endl;
modificar(v, a, l, l + (r - l + 1)/2 - 1, 2*i, j);
modificar(v, a, l + (r - l + 1)/2, r, 2*i + 1, j);
}
int consultar(const vector<int> &a, const int &x, const int &l, const int &r, const int &i, const int &j) {
if (l > j || r < i) {
return 0;
}
if (l >= i && r <= j) {
return a[x];
}
return consultar(a, 2*x, l, l + (r - l + 1)/2 - 1, i, j) ^ consultar(a, 2*x + 1, l + (r - l + 1)/2, r, i, j);
}
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
int n_odd = (n + 1) / 2, n_even = n / 2;
while (__builtin_popcount(n_odd) > 1) n_odd += LSOne(n_odd);
while (__builtin_popcount(n_even) > 1) n_even += LSOne(n_even);
cout << n_odd << ' ' << n_even << '\n';
vector<int> odd(2 * n_odd), even(2 * n_even);
for (int i = 0; i < n; ++i) {
if (i%2) {
cin >> even[n_even + i/2];
}else {
cin >> odd[n_odd + i/2];
}
}
for (int i = n_odd - 1; i > 0; --i) {
odd[i] = odd[i * 2] ^ odd[i * 2 + 1];
}
for (int i = n_even - 1; i > 0; --i) {
even[i] = even[i * 2] ^ even[i * 2 + 1];
}
// for (int i = 0; i < 2*n_odd; ++i) {
// cout << ' ' << odd[i];
// }
// cout << '\n';
// for (int i = 0; i < 2*n_even; ++i) {
// cout << ' ' << even[i];
// }
// cout << endl;
while (q--) {
int accion; cin >> accion;
if (accion == 1) { //rescan
int i, j; cin >> i >> j; --i;
if (i%2) {
modificar(even[n_even + i/2] ^ j, even, 0, n_even - 1, 1, i/2);
}else {
modificar(odd[n_odd + i/2] ^ j, odd, 0, n_odd - 1, 1, i/2);
}
// for (int i = 0; i < 2*n_odd; ++i) {
// cout << ' ' << odd[i];
// }
// cout << '\n';
// for (int i = 0; i < 2*n_even; ++i) {
// cout << ' ' << even[i];
// }
// cout << endl;
}else { //query
int l, u; cin >> l >> u; --l; --u;
int n_elem = u - l + 1;
// cout << n_elem << endl;
if (n_elem%2) {
if (l%2) {
// cout << "caso b" << endl;
cout << consultar(even, 1, 0, n_even - 1, l/2, u/2) << '\n';
}else {
// cout << "caso a" << endl;
cout << consultar(odd, 1, 0, n_odd - 1, l/2, u/2) << '\n';
}
}else {
cout << "0\n";
}
}
}
cout.flush();
return EXIT_SUCCESS;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
8528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
