Submission #1205350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205350		mehralii	XORanges (eJOI19_xoranges)	C++20	55 / 100	1093 ms	2220 KiB

xoranges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define MAXN 1000005
#define LOG (int)log2(MAXN)+1

const int INF = 1e18;
const int MOD = 998244353;
const double EPS = 1e-8;

/*
	a xor (b xor c) = a xor b xor c
	a xor b xor a = b
		||
		\/
	a1 xor a2 xor (a1 xor a2) = a1 xor a2 xor a1 xor a2 = 0

	xor - ^
	a1 ^ a2 ^ a3 ^ (a1^a2) ^ (a2 ^ a3) ^ (a1^a2^a3) = a1 ^ a2 ^ a3 ^ a1 ^ a2 ^ a2 ^ a3 ^ a1 ^ a2 ^ a3 =
	= a1 ^ a3

	query(l, r) = ?
	essentially it's xor of all sliding windows in [l,r].
	let's see how many times the i-th element occurs in a sliding window of length k
	freq[i-th element] = min(i-l+1, r-i+1, k)
	We need to know the sum for all k, then the i-th element participates in xor if the sum is odd for it,
	and does not participate if it is even.	

	Observation 1:
	cnt[i-th element] = (r-i+1)*(i-l+1)

	So we can answer queries in O(n*q) 12+18+25 = 55p.
	
*/

void solve(){
	int n, q;
	cin >> n >> q;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	int t, l, r;
	while(q--){
		cin >> t >> l >> r;
		if(t==1){
			a[l] = r;
		}else{
			int res = 0, cnt;
			for(int i = l; i <= r; i++){
				cnt = (r-i+1)*(i-l+1);
				if(cnt&1) res ^= a[i];
			}
			cout << res << '\n';
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);
    int t = 1;
    //cin >> t;
	for(int i = 1; i <= t; i++){
		//cout << "Case " << i << ": ";
		solve();
	}
    return 0;
}

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