Троє з Простоквашино
- Дядько Федір, Дядько Федір, я навчився будувати дерево відрізків.
- Зачека, Шарик, я зайнятий.
- Ну Дядько Федір, ну подивись який я код написав:
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 – елементи масиву.
Вихідні дані
Виведіть єдине число – відповідь до задачі.