动态维护中位数
开一个大根堆一个小根堆，一个用于维护较小的一半的最大值，一个用于维护较大一半的最小值，每次输入之后通过调整堆保证两半区分，时间复杂度为 $O(\log n)$
具体而言，有如下步骤：
+ 建立一个大根堆 $lt$，一个小根堆 $rt$ ，中位数 $mid$
+ 对于一个新数 $x$，若 $x\leq mid$，放进 $lt$ ，不然放进 $rt$
+ 循环调整 $lt,rt$ 的大小，使得 $|lt|=|rt|$，此时 $mid$ 即为所求
```cpp
struct ots {
int mid, len;
priority_queue<int>lt,rt;
void insert(int val) {
if(++len==1) return void(mid=val);
if(a<=mid) lt.push(val);
else rt.push(-val);
if(len&1==0) return;
while(lt.size()<rt.size())
lt.push(mid), mid=-rt.top(), rt.pop();
while(lt.size()>rt.size())
rt.push(-mid), mid=lt.top(), lt.pop();
}
int get() { return mid; }
};
```