{"problem":{"name":"E. Nikita and Order Statistics","description":{"content":"Nikita likes tasks on order statistics, for example, he can easily find the $k$\\-th number in increasing order on a segment of an array. But now Nikita wonders how many segments of an array there are ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF993E"},"statements":[{"statement_type":"Markdown","content":"Nikita likes tasks on order statistics, for example, he can easily find the $k$\\-th number in increasing order on a segment of an array. But now Nikita wonders how many segments of an array there are such that a given number $x$ is the $k$\\-th number in increasing order on this segment. In other words, you should find the number of segments of a given array such that there are exactly $k$ numbers of this segment which are less than $x$.\n\nNikita wants to get answer for this question for each $k$ from $0$ to $n$, where $n$ is the size of the array.\n\n## Input\n\nThe first line contains two integers $n$ and $x$ $(1 \\le n \\le 2 \\cdot 10^5, -10^9 \\le x \\le 10^9)$.\n\nThe second line contains $n$ integers $a_1, a_2, \\ldots, a_n$ $(-10^9 \\le a_i \\le 10^9)$ — the given array.\n\n## Output\n\nPrint $n+1$ integers, where the $i$\\-th number is the answer for Nikita's question for $k=i-1$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Nikita 喜欢与顺序统计相关的题目，例如，他可以轻松地在数组的某个区间内找到按递增顺序排列的第 $k$ 个数。但现在 Nikita 想知道，有多少个数组区间满足：给定的数 $x$ 是该区间内按递增顺序排列的第 $k$ 个数。换句话说，你需要找出给定数组中满足恰好有 $k$ 个数小于 $x$ 的区间数量。\n\nNikita 希望对每个 $k$ 从 $0$ 到 $n$（其中 $n$ 是数组的大小）都得到这个问题的答案。\n\n第一行包含两个整数 $n$ 和 $x$ $(1 lt.eq n lt.eq 2 dot.op 10^5, -10^9 lt.eq x lt.eq 10^9)$。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ $(-10^9 lt.eq a_i lt.eq 10^9)$ —— 给定的数组。\n\n请输出 $n + 1$ 个整数，其中第 $i$ 个数是 Nikita 的问题在 $k = i -1$ 时的答案。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $x$ $(1 lt.eq n lt.eq 2 dot.op 10^5, -10^9 lt.eq x lt.eq 10^9)$。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ $(-10^9 lt.eq a_i lt.eq 10^9)$ —— 给定的数组。\n\n## Output\n\n请输出 $n + 1$ 个整数，其中第 $i$ 个数是 Nikita 的问题在 $k = i -1$ 时的答案。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the size of the array, $ x $ a target value, and $ a = [a_1, a_2, \\dots, a_n] $ the given array.\n\nDefine a binary array $ b $ of length $ n $, where:\n$$\nb_i = \n\\begin{cases}\n1 & \\text{if } a_i < x \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\nFor each segment $ [l, r] $ with $ 1 \\leq l \\leq r \\leq n $, let $ s_{l,r} = \\sum_{i=l}^r b_i $ be the number of elements in the segment strictly less than $ x $.\n\nWe are to compute, for each $ k \\in \\{0, 1, \\dots, n\\} $, the number of segments $ [l, r] $ such that $ s_{l,r} = k $.\n\nLet $ c_k $ denote the number of segments with exactly $ k $ elements less than $ x $. Then output $ c_0, c_1, \\dots, c_n $.\n\n---\n\n**Formal Statement:**\n\nGiven:\n- Array $ a \\in \\mathbb{Z}^n $\n- Target $ x \\in \\mathbb{Z} $\n\nDefine:\n- $ b_i = \\mathbb{1}_{a_i < x} $ for $ i = 1, \\dots, n $\n\nObjective:\nFor each $ k = 0, 1, \\dots, n $, compute:\n$$\nc_k = \\left| \\left\\{ (l, r) \\in [1, n]^2 \\mid l \\leq r \\text{ and } \\sum_{i=l}^r b_i = k \\right\\} \\right|\n$$\n\nOutput: $ c_0, c_1, \\dots, c_n $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF993E","tags":["chinese remainder theorem","fft","math"],"sample_group":[["5 3\n1 2 3 4 5","6 5 4 0 0 0"],["2 6\n-5 9","1 2 0"],["6 99\n-1 -1 -1 -1 -1 -1","0 6 5 4 3 2 1"]],"created_at":"2026-03-03 11:00:39"}}