- Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
- Подожди, Шарик, я занят.
- Ну Дядя Федор, ну смотри какой я код написал:
int build(int v, int left, int right) {
if (left == right) {
t[v] = a[left];
return 0;
}
int mid = (left+right) / 2;
build(v*2, left, mid);
build(v*2+1, mid+1, right);
t[v] = max(t[v*2], t[v*2+1]);
return 0;
}
int get_max(int v, int left, int right, int lpos, int rpos) {
if (left == lpos right == rpos)
return t[v];
if (lpos > rpos)
return -1;
int mid = (left+right) / 2;
return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),
get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));
}
- Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из n неотрицательных чисел и число k, а ты мне скажешь сколько существует таких пар l; r (1 ≤ l ≤ r ≤ n), что функция, вызванная следующим образом
get_max(1, 1, n, l, r)
вернет значение равное k. Можно считать, что перед этим была вызвана функция
build(1, 1, n)
- Хорошо, Дядя Федор!
В первой строке находятся число n (1 ≤ n ≤ 10^6) - количество элементов в массиве и k (1 ≤ k ≤ 10^9) - значение, которое должна вернуть функция. В следующей строке находится n неотрицательных чисел, не превышающих 10^9 - элементы массива.
Выведите единственное число – ответ на задачу.