Можно построить массив где a[i] - столбец монстра на i-ой строке.
Задачу я свел к тому чтобы найти количество подотрезков (l, r) что max(a[l], a[l + 1], ..., a[r]) - min(a[l], a[l + 1], ..., a[r]) == r - l .
Так как на строках (l, r) нужно чтобы находилось r - l + 1 монстров, то нужно чтобы они стояли подряд к друг другу. Так я свел задачу и писал разделяй и властвуй.
Пусть mx1[i], mn1[i] это максимум и минимум на префиксе i в правой части, mx2[i], mn2[i] максимум и минимум на суффиксе i в левой части.
Чтобы считать количество таких подотрезков я писал разделяй и властвуй. Пусть$(l, r)$ в разных частях и я разделил их на четыре случая :
1, 2) Минимум и максимум находятся в одной части : тогда если смотрим правую часть, то l = i - mx1[i] + mn1[i], потому что r - l = mx1[i] - mn1[i], аналогично когда смотрим левую часть.
3, 4) Минимум и максимум в разных частях : тогда если максимум в правой части, а минимум нет, то r - mx1[r] = l - mn2[l], чтобы считать количество таких l - mn2[l] я заранее хранил массив векторов, где каждый вектор обозначает позиции с таким l - mn2[l]. Аналогично для левой части
Чтобы брать подходящие l я использовал два указателя.
Не могу найти баг в коде, нужна помощь.