<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
第一行为两个正整数n和b ，第二行为1~n 的排列。
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
输出一个整数，即中位数为b的连续子序列个数。
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
7 4 
5 7 2 4 3 1 6
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
4 
Hint 
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6} 
N&lt;=100000
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
从一串数字中(无规律)寻找一个子串,使得该子串的中位数为要求的数,求子串的组数
由于数字本身没有规律,而寻找中位数需要规律,因此如果暴力解决需要 <code>O(n3logn)</code> 
显然这种时间复杂度很不靠谱
由于数字不存在重复( <code>1 ~ n</code> ),并且选取的子串的数字个数必然是奇数,因此可以采用一些性质来计算
首先,中位数是一串数中,比它大的数和比它小的数个数相同的数 
因此可以先将数据处理成是否比要求的数大的形式(大于记为 <code>1</code> ,小于记为 <code>2</code> ,等于记为 <code>0</code> ) 
然后再使用 <code>O(n)</code> 的时间处理信息,分别计算从目标的数向左、向右抵消后仍然比该数大的个数 
用 <code>map</code> 记录一侧的的数达到某个数的组数,然后在另一侧将能与其抵消的相加起来,最后的数就是答案 
( <code>0</code> 要特殊考虑)
样例解释如下:
<table>
<thead>
<tr>
<th style="text-align:center">数字</th>
<th style="text-align:center">1</th>
<th style="text-align:center">2</th>
<th style="text-align:center">3</th>
<th style="text-align:center">4</th>
<th style="text-align:center">5</th>
<th style="text-align:center">6</th>
<th style="text-align:center">7</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">数据</td>
<td style="text-align:center">5</td>
<td style="text-align:center">7</td>
<td style="text-align:center">2</td>
<td style="text-align:center">4</td>
<td style="text-align:center">3</td>
<td style="text-align:center">1</td>
<td style="text-align:center">6</td>
</tr>
<tr>
<td style="text-align:center">第一次处理</td>
<td style="text-align:center">+1</td>
<td style="text-align:center">+1</td>
<td style="text-align:center">-1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">-1</td>
<td style="text-align:center">-1</td>
<td style="text-align:center">+1</td>
</tr>
<tr>
<td style="text-align:center">第二次处理</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">-1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">-1</td>
<td style="text-align:center">-2</td>
<td style="text-align:center">-1</td>
</tr>
</tbody>
</table>
将左侧(包括目标数)的数映射成 <code>map</code> 有
<table>
<thead>
<tr>
<th style="text-align:center">n</th>
<th style="text-align:center">-1</th>
<th style="text-align:center">0</th>
<th style="text-align:center">1</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">map</td>
<td style="text-align:center">1</td>
<td style="text-align:center">2</td>
<td style="text-align:center">1</td>
</tr>
</tbody>
</table>
则针对右侧的数据,结果为 <code>ans = 2 + map[1] + map[2] + map[1]</code> 
其中 <code>2</code> 是 <code>map</code> 里 <code>0</code> 的个数
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cmath&gt;
#include &lt;cstring&gt;
#include &lt;iomanip&gt;
#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;string&gt;
#include &lt;vector&gt;
#include &lt;bitset&gt;
#include &lt;functional&gt;

using namespace std;

typedef long long LL;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 100005;

int n,k;
int a[maxn];
int dp[maxn];

map&lt;int,int&gt; m;

bool Do() {

 if(!(cin &gt;&gt; n &gt;&gt; k))
 return false;

 int pos;
 for(int i = 0;i &lt; n;i++) {
 cin &gt;&gt; a[i];
 if(a[i] == k)
 pos = i;
 }

 m.clear();
 dp[pos] = 0;
 int ans = 1;
 m.insert(pair&lt;int,int&gt;(0,1));

 for(int i = pos - 1;i &gt;= 0;i--) {
 dp[i] = dp[i + 1] + ((a[i] &gt; k) ? 1 : -1);
 
 if(dp[i] == 0)
 ans++;

 if(m.count(dp[i])==0)
 m.insert(pair&lt;int,int&gt;(dp[i],0));
 m[dp[i]]++;
 }

 for(int i = pos + 1;i &lt; n;i++) {
 dp[i] = dp[i - 1] + ((a[i] &gt; k) ? 1 : -1);

 if(m.count(-dp[i]) == 1)
 ans += m[-dp[i]];
 }

 cout &lt;&lt; ans &lt;&lt; endl;

 return true;
}

int main() {
 cin.tie(0);
 cin.sync_with_stdio(false);

 while(Do());

 return 0;
}
</pre>

HYSBZ 1303.中位数图