#include // For scanf, printf (often faster than C++ iostreams) #include // For std::vector container #include // For std::sort // Define a structure to hold the values from array B and their original indices. // This is needed because we will sort B based on values, but need to output // the counts in the original order. struct Query { long long value; // The value from array B int original_index; // The original index (0 to M-1) of this value in B }; // Custom comparison function used to sort the Query structs based on their 'value' field. // This is passed as the third argument to std::sort. bool compareQueries(const Query& a, const Query& b) { // Sort primarily based on the 'value'. The relative order of queries with the same value // doesn't impact correctness, as std::sort is stable or we process them together anyway. return a.value < b.value; } int main() { int N, M; // Read the sizes of arrays A and B. // Using scanf is generally preferred in competitive programming for speed. // Basic error checking on scanf return value is good practice. if (scanf("%d %d", &N, &M) != 2) { // Handle potential input error (though often omitted in contests) return 1; } // Use std::vector for dynamic arrays. It's safer and more convenient than raw arrays. // Initialize vector A with size N to avoid potential reallocations during input reading. std::vector A(N); for (int i = 0; i < N; ++i) { // Read each element of A. Use %lld format specifier for long long. if (scanf("%lld", &A[i]) != 1) { return 1; // Handle input error } } // Read the elements of B and store them along with their original indices // in a vector of Query structs. Initialize with size M. std::vector B_indexed(M); for (int i = 0; i < M; ++i) { // Read the value B_i if (scanf("%lld", &B_indexed[i].value) != 1) { return 1; // Handle input error } // Store its original index i B_indexed[i].original_index = i; } // Sort array A in non-decreasing order. This is crucial for the efficient counting step. // std::sort has an average time complexity of O(N log N). std::sort(A.begin(), A.end()); // Sort the vector of queries (B_indexed) based on their 'value' field. // We use the custom comparison function `compareQueries`. // This groups identical query values together, allowing us to process them efficiently. // Time complexity is O(M log M). std::sort(B_indexed.begin(), B_indexed.end(), compareQueries); // Create the result vector C of size M to store the counts. // std::vector initializes elements to 0 by default. std::vector C(M); int idxA = 0; // Pointer (index) for iterating through the sorted array A. int idxB = 0; // Pointer (index) for iterating through the sorted array B_indexed. // Implement the two-pointer (or coordinate compression / sweep-line style) approach. // Iterate through the sorted queries (B_indexed). while (idxB < M) { // Get the target value for the current block of queries. long long current_target_value = B_indexed[idxB].value; // Phase 1: Advance the pointer idxA in array A. // Move idxA forward as long as the element A[idxA] is strictly less than the target value. // This efficiently skips elements in A that are smaller than the current query value. while (idxA < N && A[idxA] < current_target_value) { idxA++; } // After this loop, either idxA == N (we reached the end of A) // or A[idxA] >= current_target_value. // Phase 2: Count occurrences of current_target_value in A. int count = 0; // Initialize count for this target value. // Check if we are within the bounds of A and if the element at idxA matches the target value. if (idxA < N && A[idxA] == current_target_value) { // If found, count all consecutive occurrences of this value starting from idxA. int start_idxA = idxA; // Remember the starting index of this sequence. // Keep advancing idxA as long as we see the target value. while (idxA < N && A[idxA] == current_target_value) { idxA++; } // The number of occurrences is the difference between the final and starting indices. count = idxA - start_idxA; // Importantly, after counting, idxA is already positioned correctly // for the search of the *next distinct* target value. It points to the // first element strictly greater than current_target_value (or N). } // If the target value was not found (A[idxA] > current_target_value or idxA == N), // the count remains 0. // Phase 3: Assign the computed count to all queries in B_indexed that have this target value. // Since B_indexed is sorted by value, all queries for current_target_value form a contiguous block. // Iterate through this block. while (idxB < M && B_indexed[idxB].value == current_target_value) { // Use the stored original_index to place the count in the correct position in the result vector C. C[B_indexed[idxB].original_index] = count; // Move to the next query in B_indexed. idxB++; } // After this loop, idxB points to the first query with a value greater than // current_target_value (or idxB == M), ready for the next iteration of the outer while loop. } // Print the final counts stored in vector C. for (int i = 0; i < M; ++i) { // Print each count followed by a space, except for the last count, // which should be followed by a newline character. printf("%d%c", C[i], (i == M - 1) ? '\n' : ' '); } return 0; // Indicate successful execution. }