У даній задачі необхідно було написати декілька перевірок для
визначення властивостей заданого символу. Для перевірки, чи символ є
літерою англійського алфавіту, можна скористатися вбудованими функціями
або методами. Наприклад, у C++ це функція isalpha, а в
Python — метод isalpha. Для розрізнення великих і малих
літер можна використати isupper та islower у
C++ або відповідні методи в Python. Також можна виконати перевірку на
належність символа до діапазонів, наприклад,
if (’a’ <= ch and ch <= ’z’) для малих літер та
if (’A’ <= ch and ch <= ’Z’) для великих.
Для визначення порядкового номера символу в алфавіті зручно
скористатися властивостями того, як символи кодуються в комп’ютері.
Кожен символ має свій спеціальний код — ASCII-код. Наприклад, велика
літера A має ASCII-код \(65\), літера B — код \(66\), ..., літера Z — код
\(90\). Малі літери теж мають свої
коди: a — \(97\),
b — \(98\), ...,
z — \(122\). Не потрібно
знати напам’ять коди для всіх букв — достатньо лише знати, що великі
букви в алфавітному порядку від A до Z мають
послідовні коди. Те саме виконується й для малих букв — малі букви в
алфавітному порядку від a до z також мають
послідовні коди.
ASCII-коди дозволяють легко обчислити порядковий номер будь-якої
літери в алфавіті. Для знаходження номера великої букви треба відняти
код літери A від її коду й додати одиницю. Для малої ж
букви від її коду треба відняти код літери a й додати
одиницю.
У C++ для великої букви це можна зробити так:
c - ’A’ + 1, а для малої ось так:
c - ’a’ + 1.
У Python ord(c) - ord(’A’) + 1 або
ord(c) - ord(’a’) + 1.
Якщо символ не є літерою, необхідно перевірити, чи це цифра. Для
цього можна скористатися функцією isdigit у C++ або методом
isdigit у Python. Альтернативно, можна перевірити, чи
символ є в діапазоні ’0’ до ’9’,
використовуючи умову
if (’0’ <= ch and ch <= ’9’).
Якщо символ не є ні літерою, ні цифрою, то він належить до категорії
спеціальних символів. У такому випадку виводимо
weird symbol.
У цій задачі, подібно до задачі «Символ», необхідно вміти перевіряти, чи символ є великою літерою. Завдяки цьому ми можемо знайти індекс \(p\), з якого починається ім’я учня. Для кожного запису журналу перша велика літера після першої (тобто друга велика літера у рядку) буде початком імені.
Маючи індекс \(p\), ми можемо побудувати новий формат для кожного учня. Спочатку виводимо всі символи з позиції \(p\) до кінця рядка, а потім додаємо всі символи від початку до \(p\) (не включаючи саму позицію \(p\)). Це забезпечить перестановку прізвища та імені у вказаному форматі.
Спробуємо спростити задану формулу. Звернемо увагу, що у виразі \(\sum_{i=l}^{r} \sum_{j=l}^{r} (-1)^{i + j} \cdot (a[i] + a[j])\) є два доданки: \((-1)^{i + j} \cdot a[i]\) та \((-1)^{i + j} \cdot a[j]\). Ці доданки симетричні з точністю до перестановки індексів \(i\) та \(j\), тому достатньо порахувати лише один з них і результат помножити на \(2\).
Зафіксуємо \(i\) і розглянемо, яке значення дає внутрішня сума по \(j\): \[\sum_{j = l}^{r} (-1)^j \cdot (-1)^i \cdot a[i] = (-1)^i \cdot a[i] \cdot \sum_{j = l}^{r} (-1)^j.\]
Нехай \(c_{l, r} = \sum_{j = l}^{r} (-1)^j\). Значення \(c_{l, r}\) залежить тільки від парності \(l\) та \(r\).
\(c_{l, r} = 0\), якщо \(l\) і \(r\) мають різну парність.
\(c_{l, r} = 1\), якщо \(l\) і \(r\) обидва парні.
\(c_{l, r} = -1\), якщо \(l\) і \(r\) обидва непарні.
Загальну формулу тепер можна записати у вигляді:
\[f(n, a, l, r) = 2 \cdot c_{l, r} \cdot \sum_{i = l}^{r} (-1)^i \cdot a[i]\]
Залишилося навчитися ефективно обчислювати суму \(\sum_{i = l}^{r} (-1)^i \cdot a[i]\). Це можна зробити за допомогою префіксних сум. \(pref_k = \sum_{i = 1}^{k} (-1)^i \cdot a[i].\)
Таким чином, обробка одного запиту відбувається за \(O(1)\) після попередньої обробки масиву за \(O(n)\). Загальний час роботи алгоритму складає \(O(n + q)\).
Розглянемо розв’язок для блоку \(l_i \le
r_i \le 10^6\). Ми будемо зберігати всі елементи, які ще не
додані до множини, у спеціальній структурі, наприклад,
std::set у C++.
Для кожного запиту \([l_i, r_i]\) з умови задачі ми:
Знаходимо перше число в
set, яке більше або рівне за \(l_i\).Якщо це число \(\leq r_i\), ми видаляємо його.
Повторюємо процес, поки всі відповідні числа не будуть вилучені.
Оскільки в нас початково було \(10^6\) чисел і ми лише видаляємо числа з множини, то ми й не можемо видалити більше елементів, ніж було початково. Таким чином, кількість операцій видалення обмежена кількістю чисел, а кожна операція пошуку або видалення виконується за \(O(\log maxR)\), де \(maxR\) — максимальне значення \(r_i\).
Загальна складність цього підходу буде \(O((q + maxR) \cdot \log maxR)\), де \(q\) — кількість запитів.
Код розв’язку мовою C++ для цього блоку
Щоб розв’язати задачу на повний бал, додамо до set не
всі можливі числа, а тільки цікаві. Цікавими є числа \(l_i\) та \(r_i+1\).
Тепер маючи всі цікаві числа, посортуємо їх. Їх можна розглядати, як координати на числовій прямій.
Далі зробимо той самий процес, що для меншого блоку, тільки тепер будемо за один раз видаляти не одне число, а цілий проміжок.