// Для двух массивов целых чисел длины N, // для всех K от 1 до N, посчитать количество общих чисел на префиксах длины K. // Числа в пределах массива могут повторяться, пересечение считается без учета кратности. // префикс длины K массива A – это первые K элементов массива A // A [1, 1] => [1], [1, 1] // B [1, 1] => [1], [1, 1] // R [1, 1] // [1, 2, 5] => [1], [1, 2], [1, 2, 5] // [1, 5, 4] => [1], [1, 5], [1, 5, 4] // [1, 1, 2]

Задача: для каждого K от 1 до N посчитать количество общих уникальных чисел в префиксах длины K двух массивов.

Идея решения:

• Использовать два множества для хранения уникальных элементов префиксов каждого массива.
• Итерироваться по индексам от 0 до N-1, добавляя элементы в соответствующие множества.
• На каждом шаге считать пересечение множеств и записывать размер пересечения.

Пример на Go:

package main

import (
	"fmt"
)

func commonPrefixCounts(A, B []int) []int {
	N := len(A)
	setA := make(map[int]struct{})
	setB := make(map[int]struct{})
	result := make([]int, N)

	for i := 0; i < N; i++ {
		setA[A[i]] = struct{}{}
		setB[B[i]] = struct{}{}

		count := 0
		for val := range setA {
			if _, exists := setB[val]; exists {
				count++
			}
		}
		result[i] = count
	}
	return result
}

func main() {
	A := []int{1, 2, 5}
	B := []int{1, 5, 4}
	res := commonPrefixCounts(A, B)
	fmt.Println(res) // Output: [1 2 2]
}

Такой подход работает за O(N*M), где M — среднее количество уникальных элементов в префиксах. Для оптимизации можно использовать структуры данных с подсчетом частот и динамическим обновлением пересечения.