Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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)); } |
[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]
вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция
[latex]build(1, 1, n)[/latex]
— Хорошо, Дядя Федор!
Входные данные:
В первой строке находятся число [latex]n \left ( 1\leq n\leq 10^{6} \right )[/latex] — количество элементов в массиве и [latex]k \left ( 1\leq k\leq 10^{9} \right )[/latex] — значение, которое должна вернуть функция. В следующей строке находится [latex]n[/latex] неотрицательных чисел, не превышающих [latex]10^{9}[/latex] — элементы массива.
Выходные данные:
Выведите единственное число – ответ на задачу.
Тесты:
| Входные данные | Выходные данные | ||
| [latex]n[/latex] | [latex]k[/latex] | [latex]elem[/latex]_[latex]tree[][/latex] | [latex]ans[/latex] |
| 5 | 3 | 1 2 3 2 3 | 11 |
| 10 | 6 | 1 4 7 6 2 4 1 9 6 6 | 7 |
| 20 | 15 | 5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6 | 43 |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int[] elem_tree = new int[n]; int ans=0, left=0, right=0; for(int i=0; i<n; i++){ elem_tree[i]=in.nextInt(); if (elem_tree[i]==k){ ans+=i-left+1; right=i; } else{ if(elem_tree[i]>k){ right=0; left=i+1; } else if(elem_tree[i]<k && right!=0) ans+=right-left+1; } } System.out.println(ans); } } |
Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.