Codeforces Round 816 (Div. 2) |
---|
Закончено |
Сережа решил срочно купить новый моноблок. Сейчас он использует VPN и поэтому, чтобы попасть на сайт, надо решить вот такую капчу.
Крутостью массива назовем минимальное количество блоков подряд идущих одинаковых чисел, на которые он разбивается.
Например, крутость массива
Вам дан массив $$$a$$$ длины $$$n$$$, а также $$$m$$$ запросов, состоящих из двух целых чисел $$$i$$$ и $$$x$$$. Запрос $$$i$$$, $$$x$$$ означает, что теперь $$$i$$$-й элемент массива $$$a$$$ равен $$$x$$$.
После каждого запроса выведите сумму крутостей всех непустых подотрезков массива $$$a$$$. Другими словами, после каждого запроса вам надо вычислять $$$$$$\sum\limits_{l = 1}^n \sum\limits_{r = l}^n g(l, r),$$$$$$ где $$$g(l, r)$$$ это крутость массива $$$b = [a_l, a_{l + 1}, \ldots, a_r]$$$.
В первой строке вводятся $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$.
В каждой из следующих $$$m$$$ строк вам дает описание запросов. Каждая строка содержит два целых числа $$$i$$$ и $$$x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^9$$$).
После каждого запроса выведите ответ на задачу в отдельной строке.
5 5 1 2 3 4 5 3 2 4 2 3 1 2 1 2 2
29 23 35 25 35
После первого запроса массив $$$a$$$ равен $$$[1, 2, 2, 4, 5]$$$, ответ равен $$$29$$$, потому что подрезки массива можно разбить на блоки:
Название |
---|