1. 二叉堆
可以再 \(\mathcal{O}(\log n)\) 的时间内支持删除，插入，查询最值操作，一般用 STL 中的优先队列实现。
堆排序
把所有数字 \(\texttt{push}\) 进去然后依次 \(\texttt{pop}\) 出来即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
洛谷 P3871 [TJOI2010] 中位数
每次插入一个数字，然后询问所有数字的中位数。
维护一个大根堆一个小根堆，使得大根堆维护的是前一半的元素，小根堆维护剩下的。每次插入视情况放到小根堆/大根堆里面。
点击查看代码
#include<bits/stdc++.h>
using namespace std ;
#define ull unsigned long long
#define ll long long
#define db double
#define random(a,b) (rand()%((b)-(a)+1)+(a))
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define vec vector
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define NO cout<<"NO"<<"\n";
#define YES cout<<"YES"<<"\n";
#define No cout<<"No"<<"\n";
#define Yes cout<<"Yes"<<"\n";
#define str string
const int N=1e5+10;
int T,n,a,m;
struct Less
{
int h[N],cnt,sz;
void up(int p)
{
for(;p>1&&h[p]<h[p>>1];p>>=1)
{
swap(h[p],h[p>>1]);
}
}
void push(int x)
{
h[++cnt]=x;
sz++;
up(cnt);
}
int size()
{
return sz;
}
int top()
{
return h[1];
}
void down()
{
int s=2;
while(s<=cnt)
{
if(s<cnt&&h[s|1]<h[s]) s++;
if(h[s]<h[s>>1])
{
swap(h[s],h[s>>1]);
s<<=1;
}
else break;
}
}
void pop()
{
h[1]=h[cnt--];
down();
sz--;
}
}q1;
struct Greater
{
int h[N],cnt,sz;
void up(int p)
{
for(;p>1&&h[p]>h[p>>1];p>>=1)
{
swap(h[p],h[p>>1]);
}
}
void push(int x)
{
h[++cnt]=x;
sz++;
up(cnt);
}
int size()
{
return sz;
}
int top()
{
return h[1];
}
void down()
{
int s=2;
while(s<=cnt)
{
if(s<cnt&&h[s|1]>h[s]) s++;
if(h[s]>h[s>>1])
{
swap(h[s],h[s>>1]);
s<<=1;
}
else break;
}
}
void pop()
{
h[1]=h[cnt--];
down();
sz--;
}
}q2;
void Push(int x)
{
if(!q1.size()&&!q2.size())
{
q1.push(x);
return;
}
else if(!q2.size())
{
q2.push(x);
if(q1.top()<q2.top())
{
swap(q1.h[1],q2.h[1]);
}
return;
}
else if(x>=q1.top())
{
q1.push(x);
if(abs(q1.size()-q2.size())>1)
{
q2.push(q1.top());
q1.pop();
}
return;
}
else
{
q2.push(x);
if(abs(q1.size()-q2.size())>1)
{
q1.push(q2.top());
q2.pop();
}
}
}
int mid()
{
if((q1.size()+q2.size())&1)
{
return q1.size()>q2.size()?q1.top():q2.top();
}
else return q2.top();
}
void solve()
{
cin>>n;
For(i,1,n)
{
cin>>a;
Push(a);
}
cin>>m;
while(m--)
{
str opt;
cin>>opt;
if(opt=="mid")
{
cout<<mid()<<"\n";
}
else
{
cin>>a;
Push(a);
}
}
}
int main ( )
{
ios::sync_with_stdio(false);
cin.tie(0);
srand(time(0));
// cin >> T ;
// while ( T -- )
solve();
return 0;
}
洛谷 P1631 序列合并
有两个长度为 \(N\) 的单调不降序列 \(A,B\)，在 \(A,B\) 中各取一个数相加可以得到 \(N^2\) 个和，求这 \(N^2\) 个和中最小的 \(N\) 个。
令 \(c_{i,j}=A_i \times B_j\)。维护一个堆，第 \(1\) 大的数一定是 \(c\) 中第一列的数，所以将这 \(N\) 个数压入堆中，取出堆中的最大值是 \(c_{i,j}\)，那么 \(c_{i+1,j}\) 也可能成为答案，加入堆中，重复 \(N\) 次即可。
洛谷 P1090 [NOIP2004 提高组] 合并果子
有 \(n\) 堆石子，每次你可以选择任意不同的两堆合并，代价是两堆石子的个数之和。求合并成一堆的最小代价。
考虑贪心，每次取两堆最小的石子合并，将新的石子堆放回，递归成为一个 \(i-1\) 的问题，考虑用堆优化，时间复杂度 \(\mathcal{O}(n \log n)\)。
洛谷 P2672 [NOIP2015 普及组] 推销员
一条街上有n个白点，坐标依次是 \(x_1 \sim x_n\)，有个人一开始在 \(0\)。选择第 \(i\) 个点涂黑要付出 \(a_i\) 的代价（必须走到这个点）。最后必须回到 \(0\)。选出某k个点涂黑的代价是这 \(k\) 个点的 \(a\) 的和，加上两倍的坐标最大值。
对每个 \(k=1 \sim n\) 求，涂黑恰好 \(k\) 个不同的点的最大代价。
猜一个结论，\(k=i\) 的答案一定是在 \(k=i-1\) 的最优解的基础上再选一个最优的点得来的，发现是对的，那么就可以写出 \(\mathcal{O}(n^2)\) 的暴力。
考虑优化。预处理一个 \(pre\) 数组，\(pre_i\) 表示 \(i \sim n\) 中选择一个新的最远点可以得到的最大值。假设现在要求 \(k=i\) 的答案，\(k=i-1\) 时选择的最远点的位置是 \(pos\)，分类讨论:
- 如果要在 \(pos\) 右边选点，那么答案就是 \(pre_{pos+1}\)。
- 如果在左边选点，那么就要遍历 \(1 \sim pos-1\) 查找 \(a_i\) 最大的点，这可以用堆优化，那么答案就是堆顶元素。
将左右两边的答案比较一下如果左边的更大，那就选左边的，将堆顶元素删去即可，否则选右边的，此时最远点发生了变化，那么就要把 \(pos+1 \sim pos'-1\) 的元素入队，就做完了。
标签：,q1,q2,int,push,define,size From： https://www.cnblogs.com/zhuluoan/p/18452414