程序设计天梯赛L3-2(对顶堆 || 树状数组+二分 || vector的insert函数)

题目 题意: 维护栈的插入、删除、查询中值操作。操作次数n = 1e5,操作数x = 1e5.显然，难点在于如何O(logn)时间内求出中值。 思路:   1. 对顶堆，以前做过一个类似的题，什么动态中位数。在这个题里不能用优先队列实现，要用multiset实现。因为有删除操作，堆不好实现。同时维护down和up两个小顶堆，每次从up中取出最小值，即中值。对于插入和删除根据情况写写，关键在于懂得每次操作后adjust的思想。每次取出down中的最大值即可，只需始终满足如下条件即可:   2. 树状数组+二分. 观察到值域只有1e5，可以通过树状数组维护新增与删除的值。二分值域来判断是否>=(n+1)/2个数.   3. 利用vector的insert函数，我一个vector维护栈，另一个vector动态增加、删除，维护递增序列。这就用到了insert函数，va.insert(lower_bound(va.begin(),va.end(),x),x),将x插入到>=x的第一个数之前。动态维护了递增序列。 时间复杂度: O(nlogn) || O(n(logn)^2) || O(n*logn) 代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i= down中的最大值
//且down.size() >= up.size() && down.size() >n;
   for(int i=0;i>s;
   	   if(s[1] == 'o')
   	   {
   	   	   if(!va.size())
   	   	   {
   	   	   	  cout