{"problem":{"name":"E2. Median on Segments (General Case Edition)","description":{"content":"You are given an integer sequence $a_1, a_2, \\dots, a_n$. Find the number of pairs of indices $(l, r)$ ($1 \\le l \\le r \\le n$) such that the value of median of $a_l, a_{l+1}, \\dots, a_r$ is exactly t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1005E2"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence $a_1, a_2, \\dots, a_n$.\n\nFind the number of pairs of indices $(l, r)$ ($1 \\le l \\le r \\le n$) such that the value of median of $a_l, a_{l+1}, \\dots, a_r$ is exactly the given number $m$.\n\nThe median of a sequence is the value of an element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.\n\nFor example, if $a=[4, 2, 7, 5]$ then its median is $4$ since after sorting the sequence, it will look like $[2, 4, 5, 7]$ and the left of two middle elements is equal to $4$. The median of $[7, 1, 2, 9, 6]$ equals $6$ since after sorting, the value $6$ will be in the middle of the sequence.\n\nWrite a program to find the number of pairs of indices $(l, r)$ ($1 \\le l \\le r \\le n$) such that the value of median of $a_l, a_{l+1}, \\dots, a_r$ is exactly the given number $m$.\n\n## Input\n\nThe first line contains integers $n$ and $m$ ($1 \\le n,m \\le 2\\cdot10^5$) — the length of the given sequence and the required value of the median.\n\nThe second line contains an integer sequence $a_1, a_2, \\dots, a_n$ ($1 \\le a_i \\le 2\\cdot10^5$).\n\n## Output\n\nPrint the required number.\n\n[samples]\n\n## Note\n\nIn the first example, the suitable pairs of indices are: $(1, 3)$, $(1, 4)$, $(1, 5)$, $(2, 2)$, $(2, 3)$, $(2, 5)$, $(4, 5)$ and $(5, 5)$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个整数序列 $a_1, a_2, dots.h, a_n$。\n\n求满足 $1 lt.eq l lt.eq r lt.eq n$ 的下标对 $(l, r)$ 的数量，使得子序列 $a_l, a_(l + 1), dots.h, a_r$ 的中位数恰好等于给定的数 $m$。\n\n一个序列的中位数是指将序列按非降序排序后位于中间位置的元素。如果序列长度为偶数，则使用两个中间元素中靠左的那个。\n\n例如，若 $a = [ 4, 2, 7, 5 ]$，则其中位数为 $4$，因为排序后序列为 $[ 2, 4, 5, 7 ]$，两个中间元素中靠左的是 $4$。序列 $[ 7, 1, 2, 9, 6 ]$ 的中位数为 $6$，因为排序后 $6$ 位于序列正中间。\n\n编写一个程序，求满足子序列 $a_l, a_(l + 1), dots.h, a_r$ 的中位数恰好等于给定数 $m$ 的下标对 $(l, r)$（$1 lt.eq l lt.eq r lt.eq n$）的数量。\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 2 dot.op 10^5$），分别表示给定序列的长度和要求的中位数值。\n\n第二行包含一个整数序列 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 2 dot.op 10^5$）。\n\n请输出所求的数量。\n\n在第一个例子中，符合条件的下标对为：$(1, 3)$、$(1, 4)$、$(1, 5)$、$(2, 2)$、$(2, 3)$、$(2, 5)$、$(4, 5)$ 和 $(5, 5)$。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 2 dot.op 10^5$），分别表示给定序列的长度和要求的中位数值。第二行包含一个整数序列 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 2 dot.op 10^5$）。\n\n## Output\n\n请输出所求的数量。\n\n[samples]\n\n## Note\n\n在第一个例子中，符合条件的下标对为：$(1, 3)$、$(1, 4)$、$(1, 5)$、$(2, 2)$、$(2, 3)$、$(2, 5)$、$(4, 5)$ 和 $(5, 5)$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the sequence.  \nLet $ m \\in \\mathbb{Z}^+ $ be the target median value.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z}^+ $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nFor a contiguous subsequence $ A[l:r] = (a_l, a_{l+1}, \\dots, a_r) $ with $ 1 \\leq l \\leq r \\leq n $, define its **median** as the element at position $ \\left\\lfloor \\frac{r - l + 2}{2} \\right\\rfloor $ in the sorted version of $ A[l:r] $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq m \\leq 2 \\cdot 10^5 $  \n3. $ 1 \\leq a_i \\leq 2 \\cdot 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCompute the number of pairs $ (l, r) $ with $ 1 \\leq l \\leq r \\leq n $ such that the median of $ A[l:r] $ is exactly $ m $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1005E2","tags":["sortings"],"sample_group":[["5 4\n1 4 5 60 4","8"],["3 1\n1 1 1","6"],["15 2\n1 2 3 1 2 3 1 2 3 1 2 3 1 2 3","97"]],"created_at":"2026-03-03 11:00:39"}}