P1627 [CQOI2009]中位数 题解
简要题意：
给定一个 \(1\) ~ \(n\) 的排列，求以 \(b\) 为中位数的 连续子序列且长度为奇数 的个数。
显然这段序列包含 \(b\).
中位数的定义：排序后在最中间的数。
算法一
对于 \(30 \%\) 的数据，\(n \leq 100\).
由于这段序列一定包含 \(b\)，那么我们可以枚举区间 \([i,j]\) 包含 \(b\)（有类似于双指针），然后单独取出 \([i,j]\) 这段进行排序，暴力判断即可。
时间复杂度：\(O(n^3 \log n)\).
实际得分：\(30pts\).
算法二
对于 \(60 \%\) 的数据，\(n \leq 1000\).
显然我们不需要每次都把 \([i,j]\) 这段取出，可以一次次扩展。
比方说枚举 \(i\) （从 \(d\) 到 \(1\)，\(d\) 是 \(b\) 的位置），然后枚举 \(j\) 从 \(d\) 到 \(n\). 对于每个 \(j\)，只需在原来数组的基础上添上一个 \(a_j\) 即可；如果 \(j=n\) 的话，添加之后要把数组清空。
那么每次只需要插入一个数的话，我们可以用 插入排序，因为已经排序的是有序的，因为插入的位置可以用二分算出。插入操作我们不用数组维护，用 \(\text{vector}\) 维护会方便很多。
时间复杂度：\(O(n^2 \log n)\).
实际得分：\(60pts\).
算法三
对于 \(60 \%\) 的数据，\(n \leq 1000\).
抛开排序过程，我们想：因为排列的性质，不存在重复数。所以，一个连续序列的中位数为 \(b\) 当且仅当比 \(b\) 大的数的个数和比 \(b\) 小的数的个数相等。 那么，对于 \(d\) 的左边，线性 \(\text{dp}\) ，用 \(f_i\) 表示 \(i\) ~ \(d\) 比 \(i\) 大的数的个数，\(g_i\) 是小的，同理 \(d\) 的右边也推一遍。
那么，我们枚举左右端点 \(i,j\) 只需要 \(O(1)\) 判断即可。即 \(f_i + g_i = f_j + g_j\).
时间复杂度：\(O(n^2)\).
实际得分：\(60pts\).
算法四
对于 \(60 \%\) 的数据，\(n \leq 1000\).
从算法三的 \(\text{dp}\) 上入手，我们发现，\(f_i + g_i = f_j + g_j\) 等价于 \(f_i – f_j = g_i – g_j\). 所以我们只需要算出 比 \(b\) 大的数的个数与比 \(b\) 小的数的个数之差 重新作为 \(f\) 数组的状态，然后枚举端点即可。
时间复杂度：\(O(n^2)\).
实际得分：\(60pts\).
算法五
对于 \(100 \%\) 的数据，\(n \leq 10^5\).
从算法四上再优化一下，其实对于固定的一个左端点 \(i\)，我们只需要算出有多少个 \(j \geq d\) 且 \(f_i = f_j\) 即可。
也就是说，我们需要维护 区间查询相等个数。
智商不够，数据结构来凑。所以这个查询我们可以用 \(\text{Treap}\) 或者 \(\text{Splay}\) 来实现。（随便用个平衡树板子都能实现的）
时间复杂度：\(O(n \log n)\).
实际得分：\(100pts\).
算法六
对于 \(100 \%\) 的数据，\(n \leq 10^5\).
从算法五上入手，你发现 区间查询相等个数 是静态查询，不需要修改。那你可以用 权值线段树（主席树） 解决本题。
时间复杂度：\(O(n \log n)\).
实际得分：\(100pts\).
算法七
对于 \(100 \%\) 的数据，\(n \leq 10^5\).
在算法六的基础上，你发现不仅是静态，而且是固定的一个区间 \([d,n]\). 那么我们不需要用 权值线段树（可以理解为 \(n\) 棵线段树），只需要 \(1\) 棵线段树即可。
时间复杂度：\(O(n \log n)\).
实际得分：\(100pts\).
算法八
对于 \(100 \%\) 的数据，\(n \leq 10^5\).
如果你的程序在算法七止步不前，只能说明你是个天才，离最后的成功只差几步了。
固定区间维护静态相等个数，听上去很高大上啊，其实不就是个 \(\text{map}\) 吗？
某同学：我还能 %$#^%*(%&))
嗯，改成 \(\text{map}\) 之后感觉简单多了，是不是？然后我们直接省去 \(f\) 数组，直接存入 \(\text{map}\).
时间复杂度：\(O(n \log n)\).
实际得分：\(100pts\).
//为了看起来清晰 , 用了嵌套三目运算符
// q[tot+=((a[i]>b)?1:(a[i]<b)?-1:0)]++; 其实相当于这几句：
// if(a[i]>b) tot++;
// if(a[i]<b) tot--;
// q[tot]++;
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,b,wz,a[N];
int tot,sum; ll ans=0;
map<int,int> q;
int main(){
n=read(),b=read();
for(int i=1;i<=n;i++) a[i]=read(),wz=(a[i]==b)?i:wz;
for(int i=wz;i<=n;i++) q[tot+=((a[i]>b)?1:(a[i]<b)?-1:0)]++;
for(int i=wz;i>=1;i--) ans+=q[0-(sum+=(a[i]>b)?1:((a[i]<b)?-1:0))];
printf("%lld\n",ans);
return 0;
}
算法九
对于 \(200 \%\) 的数据，\(n \leq 10^7\).
（实际上是本人的一个加强）
算法八的基础上，我们可以尝试拿掉这个 \(\log\).
但是你很快发现下标虽然不超过 \(10^7\)，但是会有负数，可能有 \(-10^7\).
显然，哈希处理负下标 是这题的最终正解。
把每个下标都加上 \(n\)，解决负下标之后 \(O(1)\) 查询，拿掉 \(\text{map}\) 还解决了 \(\log\).
时间复杂度：\(O(n)\).
实际得分：\(200pts\).