Explica con palabras el algoritmo para calcular el producto escalar de dos vectores comprimidos (codificados en RLE) en una sola pasada sin descomprimirlos. ¿Cuál es la complejidad asintótica en tiempo?

Скалярное произведение двух RLE-сжатых векторов можно вычислить за один проход, не распаковывая их полностью, используя идею параллельного обхода блоков.

Каждый вектор представлен как последовательность пар (значение, длина), например: [(v1, l1), (v2, l2), ...].

Алгоритм:

1. Инициализируем два указателя на первые блоки каждого вектора.
2. На каждом шаге берем текущие блоки из обоих векторов.
3. Вычисляем минимальную длину блока minLen = min(l1, l2).
4. Добавляем к результату произведение значений блоков, умноженное на minLen: result += v1 * v2 * minLen.
5. Уменьшаем длины блоков на minLen.
6. Если длина блока в одном из векторов стала 0, переходим к следующему блоку этого вектора.
7. Повторяем, пока не пройдем все блоки обоих векторов.

Асимптотическая сложность:

• Время пропорционально суммарному количеству блоков в обоих RLE-представлениях, то есть O(n + m), где n и m — количество блоков в первом и втором векторе соответственно.

Таким образом, мы эффективно вычисляем скалярное произведение без распаковки векторов.