Условие
На нити N бусин. Цвет каждой — целое число от 1 до M. Алиса выбирает непустой непрерывный фрагмент, в котором её любимый цвет X встречается ровно один раз. Фрагменты различны, если различается начальная или конечная позиция. Найдите количество подходящих фрагментов.
Входные данные
В первых трёх строках N, M, X. Затем N цветов Aᵢ, каждый на отдельной строке. 1 ≤ N,M ≤ 2·10^5; 1 ≤ X,Aᵢ ≤ M. Ответ может превышать 32-битный целый тип.
Что вывести
Выведите одно целое число — ответ на задачу.
Как понимать условие
Фрагмент — это несколько соседних бусин, без пропусков; одна бусина тоже образует фрагмент. Цвет X должен встретиться ровно один раз, а бусины остальных цветов могут повторяться. Для [1, 2, 3, 2, 1] и X = 2 фрагмент с позициями [1, 3] подходит: это [1, 2, 3]. Фрагмент [1, 5] не подходит, потому что двоек две, а [3, 3] — потому что двоек нет. Всего подходящих фрагментов восемь. Позиции в этом примере считаются с единицы.
Зафиксируем правый конец фрагмента
В последовательности [1, 2, 3, 2, 1] любимый цвет 2. Когда правый конец равен 3 в нумерации с единицы, допустимы левые концы 1 и 2. Если начать правее позиции 2, любимого цвета не будет.
Пусть last — последняя позиция X не правее текущего конца, previous — предыдущая позиция X. Чтобы внутри был ровно один X, левый конец должен лежать строго правее previous и не правее last. Таких позиций last − previous.
Проверьте рассуждение
Цвета [2, 1, 2, 1, 2], X = 1. Сколько подходящих фрагментов заканчивается на последней позиции?
Один проход
Используем нумерацию с нуля. До первого X положим previous = last = −1: разность равна нулю. При очередном X запоминаем previous = last, затем last = i. После обработки каждого элемента прибавляем last − previous к ответу.
Каждый подходящий фрагмент учитывается один раз — при обработке своего правого конца. Поэтому сумма вкладов равна общему числу фрагментов. Время — O(N). Вход читается по одной бусине, поэтому дополнительная память — O(1).
Другой способ проверить формулу
Можно фиксировать саму бусину X. Если её позиция p, соседние позиции X — q и r, то левый конец выбирается p − q способами, правый — r − p способами. Вклад равен (p − q)(r − p). За границами массива используются q = −1 и r = N.
При одном X в середине нити длины 200000 ответ может превысить 10 миллиардов. В C++ нужен long long. Если X отсутствует, ответ 0; если все бусины имеют цвет X, подходят только одноэлементные фрагменты, и ответ N.
Реализация на Python
n = int(input())
m = int(input())
x = int(input())
previous = last = -1
answer = 0
for i in range(n):
color = int(input())
if color == x:
previous, last = last, i
answer += last - previous
print(answer)
Реализация на C++17
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n,m,x; cin >> n >> m >> x;
long long previous=-1,last=-1,answer=0;
for(int i=0;i<n;++i) {
int color; cin >> color;
if(color==x) { previous=last; last=i; }
answer += last-previous;
}
cout << answer << "\n";
}