n 只宝可梦宝可梦有两个属性，攻击值 $$B每当捕捉到一只新的宝可梦 $$T，小智有两种方法判断这只宝可梦是否是无用的

0

每当捕捉到一只新宝可梦，需要输出当前共有几只無用宝可梦$0^{}0{}_{}{}_{}{0}^{}$

• 起点为最小值处，终点为最大值处
• 上凸壳维护上半部分下凸壳维护下半部分

• 上下凸殼判断一个点是否删除的代码不同，但均使用叉乘
  P是否该删去左边点为 $$
0 0

---

给定序列长度n每输入奇数个数，求其中位数一次最后输出所有中位数。

分析：对顶堆做法开两个堆，大根堆与小根堆其中大根堆用来存排序后排名为1~n/2的数，小根堆用来存n/2+1~n的数

那么维护好这两个堆，每次查询中位数只需要访问小根堆的堆顶即是中位数

大根堆堆中的数字一定全部小于堆顶，小根堆堆中的数字一定全部大于等于堆顶相当于排序后序列前一半的数字在大根堆，后一半在小根堆

那么如何维护呢，我们需要解决两个問题：一是如何插入元素向哪个堆插入；而是当某一个堆中的元素过多时，需要弹出元素将其放入另一个堆中。

首先解决1：选择小根堆的堆顶元素作为分界点比他小的元素都放到大根堆，比他大的放到小根堆

其次解决2：:我们设q1,q2分别为大根堆，小根堆,n1,n2为大根堆元素个數n2位小根堆元素个数，总元素个数为n

那么不需要调整的情况：n2=n1+1;

    2.1：当n1>n2时 序列超过一半的元素在大根堆中，n2<floor(n*1.0/2)那么此时排名在最中间的元素一定不在小根堆中，此时小根堆的堆顶元素不是中位数故将大根堆的堆顶插入小根堆中。(参考序列 9 8 7 6 5 4)

//大根堆存放排名1~m/2的元素,小根堆存放排名为m/2+1~m的元素;

当然中位数还有另一种解法，即线段树做法记录区间和，每次更新一次新加入的节点在找一下区间第(i+1)/2大数就是中位数。

对于一棵树每次询问删掉两棵孓树的直径

每次删掉两颗子树相当于在dfs$$序上维护一段区间内点集的直径
每次询问的时候考虑合并
合并两个相邻联通块新的直径的两个端点肯定是原来两个联通块的直径的两个直径的端点