Official Analysis (C++)

Explanation

Let's expand the rule for $f(j)$.

$f(j) = |(\sum_{i = 1}^{n} (-1)^{i - 1} \cdot a_i) - (\sum_{i = 1}^{n} (-1)^{i - 1} \cdot b_{i + j})|$

Let's call the added value $k$ and the $a$'s alternating sum $v$.

Note that for each query, adding $k$ to an even-length segment won't make a difference because they'll cancel themselves. Otherwise, $v$ will differ by $k$ (it's not canceled by the following element).

This means that we can precompute $v$ in $\mathcal{O}(N)$ time.

What about $b$? We can compute each segment of $n$ elements with two pointers, since $b$'s values never change.

However, checking every value of $j$ will surely TLE. Instead, we can notice that since we're calculating absolute value, we only care about the two closest elements on either side of it. Thus, we'll binary search on the alternating sums of $b$.

Implementation

Time Complexity: $\mathcal{O}(N + (M + Q)\log M)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>
using std::vector;

int main() {
	int n;
	int m;
	int q;
	std::cin >> n >> m >> q;