Оптимізація алгоритму
Limits: 4 sec., 512 MiB
Школяре, ти вмієш оптимізовувати алгоритми?
Тобі задано алгоритм, який для заданого масиву \(a\) з \(n\) цілих чисел обчислює на проміжку \(a[l \dots r]\) деяке значення.
Ось псевдокод функції \(f\), яка реалізовує алгоритм:
У циклі for змінні \(i\) та \(j\) перебирають значення від \(l\) до \(r\) включно. У псевдокоді умова \((i+j) \% 2 = 0\) перевіряє, чи \((i+j)\) — парне.
Цей алгоритм написаний неоптимально. Твоє завдання — оптимізувати його.
Тобі заданий масив \(a\) з \(n\) цілих чисел.
Ти повинен опрацювати таких \(q\) запитів.
\(l\ r\) — обчислити значення функції \(f(n, a, l, r)\).
Зауваж, що якщо ти реалізуєш алгоритм так, як у псевдокоді, ти не набереш повний бал — тобі потрібно реалізувати його оптимально.
Input
У першому рядку записано ціле число \(n\) — кількість елементів у масиві.
У другому рядку задано \(n\) цілих чисел \(a_i\) — елементи масиву.
У третьому рядку задано ціле число \(q\) — кількість запитів.
У наступних \(q\) рядках задано по два цілі числа \(l\), \(r\) — межі проміжку в запиті.
Output
У \(q\) рядках виведи відповіді на всі запити.
Constraints
\(1 \le n, q \le 3 \cdot 10^5\),
\(1 \le l_i \le r_i \le n\),
\(1 \le a_i \le 10^9\).
Оцінювання складається з таких блоків:
по 1 балу за кожен приклад з умови,
7 балів: \(q = 1\), \(l_i = 1, r_i = n\), \(n\) — парне,
13 балів: \(q = 1\), \(l_i = 1, r_i = n\), \(n \le 3 \cdot 10^3\), \(a_i \le 10^3\),
10 балів: \(q = 1\), \(l_i = 1, r_i = n\), \(n \le 3 \cdot 10^3\), \(a_i \le 10^9\),
26 балів: \(q = 1\), \(l_i = 1, r_i = n\), \(n \le 3 \cdot 10^5\), \(a_i \le 10^3\),
20 балів: \(q = 1\), \(l_i = 1, r_i = n\), \(n \le 3 \cdot 10^5\), \(a_i \le 10^9\),
5 балів: \(q = 1\), \(n \le 3 \cdot 10^5\), \(a_i \le 10^9\),
17 балів: без додаткових обмежень.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 2 3 4 2 1 4 2 4 | 0 6 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 4 7 4 7 4 1 1 5 | -4 |
Notes
Формула, яку реалізовує алгоритм:
\[s = \sum_{i = l}^{r} \sum_{j = l}^{r} (-1)^{i + j} \cdot (a_i + a_j).\]
Перший приклад:
\(f(n, a[1 \dots n], 1, 4) = 2 - 3 + 4 - 5 - 3 + 4 - 5 + 6 + 4 - 5 + 6 - 7 - 5 + 6 - 7 + 8 = 0\),
\(f(n, a[1 \dots n], 2, 4) = 4 - 5 + 6 - 5 + 6 - 7 + 6 - 7 + 8 = 6\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|