Задача №115147. Суммы модулей
Для последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и целого числа \(x\) обозначим через \(f(a, x)\) количество таких целых \(i\) от \(1\) до \(n\), что \(a_i \le x\).
Для пары последовательностей целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\) обозначим через \(g(a, b, c)\) сумму значений \(|f(a, x)-f(b, x)|\) по всем целым \(x\), лежащим в отрезке \([0, c]\). Более формально, \(g(a, b, c) = \sum_{x=0}^c |f(a, x)-f(b, x)|\).
Вам даны два целых числа \(n\) и \(c\), а также две последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\), все элементы которых лежат в отрезке \([-1, c]\). Известно, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\) .
Скажем, что пара последовательностей целых чисел \(a_1', a_2', \ldots, a_n'\) и \(b_1', b_2', \ldots, b_n'\), все элементы которых лежат в отрезке \([0, c]\), соответствует шаблону \((a, b)\), если выполняются следующие условия:
- Для всех \(i\) (\(1 \le i \le n\)), таких, что \(a_i \ne -1\), выполняется \(a_i'=a_i\).
- Для всех \(i\) (\(1 \le i \le n\)), таких, что \(b_i \ne -1\), выполняется \(b_i'=b_i\).
- Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(a_i' \le a_{i+1}'\).
- Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(b_i' \le b_{i+1}'\).
Обозначим через \(h(a, b, c)\) сумму значений \(g(a', b', c)\) по всем парам последовательностей \((a', b')\), соответствующих шаблону \((a, b)\). Вы должны посчитать \(h(a, b, c)\). Также вы должны обработать \(q\) запросов изменения последовательностей \(a\) и \(b\) и посчитать \(h(a, b, c)\) после каждого изменения. Обратите внимание, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\), ни до всех запросов, ни после какого-либо запроса .
Первая строка содержит три целых числа \(n\), \(c\) и \(q\) (\(1 \le n \le 100\,000\), \(0 \le c \le 10^9\), \(0 \le q \le 100\,000\)) — длина последовательностей \(a\) и \(b\), ограничение на значения элементов \(a\) и \(b\) и количество запросов, соответственно.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \le a_i \le c\)) — последовательность \(a\).
Третья строка содержит \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(-1 \le b_i \le c\)) — последовательность \(b\).
В следующих \(q\) строках заданы запросы изменения. Каждый запрос задается тройкой целых чисел \(t\), \(p\), \(x\) (\(1 \le t \le 2\), \(1 \le p \le n\), \(-1 \le x \le c\)). Если \(t=1\), то данный запрос меняет \(a_p\) на \(x\). Если \(t=2\), то данный запрос меняет \(b_p\) на \(x\).
Гарантируется, что до всех изменений и после каждого изменения ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).
Выведите \((q+1)\) строку. В \((i+1)\)-й строке (\(0 \le i \le q\)) выведите одно целое число — значение \(h(a, b, c)\) по модулю \(10^9+7\) после применения первых \(i\) запросов изменения.
Тесты к этой задаче состоят из 10 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
Шаблон называется корректным , если существует хотя бы одна пара последовательностей \((a'\), \(b')\), соответствующая этому шаблон.
Условия, указанные в столбце «Комментарий», выполняются до всех запросов и после каждого запроса.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(c\) | \(q\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 8 | \(n \le 5\) | \(c \le 5\) | \(q \le 100\) | 0 | |
| 2 | 10 | \(n=1\) | – | – | – | |
| 3 | 7 | \(n \le 100\) | \(c \le 100\) | \(q \le 100\) | 0, 1 | |
| 4 | 9 | \(n \le 300\) | \(c \le 300\) | \(q \le 300\) | 0, 1, 3 | |
| 5 | 15 | \(n \le 1000\) | – | \(q \le 1000\) | 0, 1, 3, 4 | |
| 6 | 7 | – | – | – | – | \(a_i, b_i \ne -1\) для всех \(i\) |
| 7 | 10 | – | – | 6 | \(a_i \ne -1\) для всех \(i\) | |
| 8 | 18 | – | – | – | – | Шаблон является корректным |
| 9 | 16 | – | – | – | 0 – 8 | |
Рассмотрим первый тест из примера. В нем \(n=3\), \(c=4\), \(q=3\). До всех запросов \(a=[-1, 1, 3]\), \(b=[1, -1, 2]\). Шаблону \((a, b)\) соответствуют следующие пары последовательностей:
- \(a'=[0, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=2\).
- \(a'=[0, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=3\).
- \(a'=[1, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=1\).
- \(a'=[1, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=2\).
В первом запросе \(t=1\), \(p=1\), \(x=2\). Этот запрос меняет \(a_1\) с \(-1\) на \(2\). Таким образом, после этого запроса \(a=[2, 1, 3]\), \(b=[1, -1, 2]\). В последовательности \(a\) нет \(-1\), поэтому в любой паре последовательностей \((a', b')\), соответствующей шаблону \((a, b)\), последовательность \(a'\) должна совпадать с \(a\). В последовательности \(a\) не выполняется условие \(a_1 \le a_2\), поэтому не существует ни одной пары последовательностей, соответствующей шаблону, а тогда \(h(a, b, 4)=0\) после первого запроса.
3 4 3 -1 1 3 1 -1 2 1 1 2 1 2 -1 2 2 2
8 0 12 5