Submission #52405806

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define intll long long
#define endl '\n'
#define TEST_CASE false

template<typename T>
void PRINT(vector<T>& arr) {
	for (int i = 0; i < int(arr.size()); i++)
		cout << arr[i] << " \n"[i == int(arr.size()) - 1];
}

// arr[i] <= x, last index of i
int last_find(vector<int>& arr, int x) {
	auto it = upper_bound(arr.begin(), arr.end(), x);
	if (it == arr.begin()) return -1;
	--it;
	return it - arr.begin();
}

// arr[i] <= x, first index of i
int first_find(vector<int>& arr, int x) {
	auto it = lower_bound(arr.begin(), arr.end(), x);
	if (it == arr.end()) return -1;
	if (*it == x) return it - arr.begin();
	if (it == arr.begin()) return -1;
	--it;
	return (*it <= x ? it - arr.begin() : -1);
}

template<typename T = int>
struct BLOCK {
	int N, block_size;
	vector<vector<T>> block;
	vector<vector<int>> B;
	vector<int> A;
	BLOCK(int n) : BLOCK(vector<int>(n, 0)) {}
	BLOCK(vector<int>& arr) : A(arr) {
		N = int(arr.size());
		block_size = 450;
		block.resize(block_size, vector<T>(block_size, 0)); // init_value
		B.resize(block_size);
		for (int i = 0; i < block_size; i++)
			build_block(i);
	}

	// 0-index
	int block_id(int i) { return (i / block_size); }

	// build BLOCK b
	void build_block(int b) {
		int l = b * block_size;
		if (l >= N) return;
		for (int i = l; i < (l + block_size); i++)
			B[b].push_back(A[i]);
		if (B[b].empty()) return;
		ranges::sort(B[b]);
		block[b][0] = B[b][0];
		for (int i = 1; i < block_size; i++)
			block[b][i] = block[b][i - 1] + (T) B[b][i];
	}

	// 1 - indexA
	// void update(int pos, T x) {
	// 	int B = block_id(pos - 1);
	// 	block[B] -= A[pos - 1]; // change OP
	// 	A[pos - 1] = x;
	// 	block[B] += A[pos - 1]; // cahnge OP
	// }

	// 1-index
	// void update_block(int pos, T x) {
	// 	int B = block_id(pos - 1);
	// 	A[pos - 1] = x;
	// 	build_block(B);
	// }

	// 1 - index
	T query(int l, int r, int x) {
		assert(1 <= l and l <= r and r <= N);
		l--, r--;
		T ans = 0; // Init Value
		for (; (l <= r) && (l % block_size != 0);) {
			ans += (T) (A[l] <= x ? A[l] : 0ll); // Cahnge OP
			l++;
		}
		for (; (l <= r) && (l + block_size - 1 <= r);) {
			int B_ = block_id(l);
			// ans += block[B];   // Change OP
			auto lb = last_find(B[B_], x);
			ans += 1ll * (lb == -1 ? 0 : block[B_][lb]);
			l += block_size;
		}
		for (; l <= r; ) {
			ans += (T)(A[l] <= x ? A[l] : 0ll);  // Change OP
			l++;
		}
		return ans;
	}
};


void solution() {

	int n;
	cin >> n;

	vector arr(n, int(0));
	for (auto &i : arr)
		cin >> i;

	BLOCK<intll> BL(arr);

	intll BEG = 0;
	int q;
	cin >> q;
	while (q--) {
		intll A, B, Y;
		cin >> A >> B >> Y;

		int l = A ^ BEG;
		int r = B ^ BEG;
		int x = Y ^ BEG;

		// cout << l << " " << r << endl;

		BEG = BL.query(l, r, x);
		cout << BEG << endl;
	}
}

int32_t main() {

	ios::sync_with_stdio(false) ; cin.tie(0) ;

	int t_c = 1, tt_c = 1;
	if (TEST_CASE) cin >> t_c;

	while (t_c--) {
		// cout << "Case " << tt_c++ << ": ";
		solution();
		// if (t_c) cout << '\n';
	}

	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int32_t main()’:
Main.cpp:137:22: warning: unused variable ‘tt_c’ [-Wunused-variable]
  137 |         int t_c = 1, tt_c = 1;
      |                      ^~~~

Judge Result