题解 P1168 【中位数】
小黑AWM
2019-04-11 23:10:46
> **这么有趣的一道链表思路题，你谷真的没有人写链表吗（翻了全部8页题解未见链表）？？？对顶堆是多么的枯燥乏味**
> *"使用链表来解此题有在线和离线两种算法，本文主要介绍离线算法，不过会用一句话来介绍在线算法。"*
### 在线算法
***
利用本题的特殊性，我们通过使用块状链表，对于每一个新插入的数二分后插入然后每次返回位置在中间的元素，将块大小设置为 $nlog_2n$ 即可实现 $O(n\sqrt{nlog_2n})$ 的复杂度，应该是没错了。
### 离线算法
***
相较于平衡树，对顶堆，分块的暴力，离线的做法更能体现出一种思维的美感。我们通过预先将所有的数字存储，标记其在原数组中的位置，然后将一个与原数组相同的数组排序，构建一个 $A_n\rightarrow POS_n$ 的一一映射，其中 $A_n$ 表示原序列中的第 $n$ 个元素，而 $POS_n$ 表示原序列中第 $n$ 个元素在排序后的序列 $\{B_n\}$ 中的位置，将 $\{B_n\}$ 按照排序后的顺序连成链表，即从链头至结尾元素大小单调递增。所以 $POS_n$ 就是 $A_n$ 在链表中的节点标号。
然后我们倒序做，原数列中每添加一个元素我们就把这个元素从链表中删去，而且如果这个元素在链表中在中位数的元素的左边那么就把中位数的指针往右移，如果在右边就往左移，保证有一个指针始终指向中位数所在的链表的节点。
code: 代码因为有读优+模板的原因略长，直接从using namespace IO;之后看起即可
```cpp
//It's supposed to die.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
using namespace std;
#define reg register
#define endfile fclose(stdin);fclose(stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
namespace IO{
char buf[1<<15],*S,*T;
inline char gc(){
if (S==T){
T=(S=buf)+fread(buf,1,1<<15,stdin);
if (S==T)return EOF;
}
return *S++;
}
inline int read(){
reg int x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
inline ll readll(){
reg ll x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
}
using namespace IO;
const int maxn = 1e6 + 10;
int n, a[maxn], pos[maxn], mid, mov, cnt, ans[maxn];
pii b[maxn];
struct Node{
int pre, nxt, val;
} List[maxn];
void insert(int node, int val){
List[++cnt].val = val;
List[cnt].pre = node;
List[cnt].nxt = List[node].nxt;
List[List[node].nxt].pre = cnt;
List[node].nxt = cnt;
}
void erase(int node){
List[List[node].pre].nxt = List[node].nxt;
List[List[node].nxt].pre = List[node].pre;
}
bool cmp(pii u, pii v){
if(u.first == v.first)
return u.second < v.second;
return u.first < v.first;
}
int main(){
n = read();
if(!(n & 1))
n--;
mid = (n+1) >> 1;
for(int i = 1; i <= n ; i++)
b[i].first = a[i] = read(), b[i].second = i;
sort(b+1, b+1+n, cmp);
for(int i = 1; i <= n; i++){
insert(cnt, b[i].first);
pos[b[i].second] = cnt;
}
for(int i = n; i >= 1; i--){
if(i & 1){
if(mov > 0)
mid = List[mid].nxt;
if(mov < 0)
mid = List[mid].pre;
mov = 0;
ans[i] = List[mid].val;
}
if(pos[i] < mid)
mov++;
if(pos[i] > mid)
mov--;
erase(pos[i]);
}
for(int i = 1; i <= n; i++)
if(i & 1)
cout << ans[i] << endl;
return 0;
}
```