分块优化vector实现平衡树，当一个vector的大小超过定长的一半时将其分裂一半，删除时进行合并操作。
但是，对于块长需要一定的人品，在数据范围1e6时，取sz=1000和1600可以，但是800或2000都不行。
template<const int sz=1600,const int inf=2147483647>
struct BlockVector{
vector<vector<int>>bv;
inline int pos(int x){
int l=0,r=bv.size()-1,re=bv.size()-1;/*初始化是最后一个块，若x是最大值那么不会有check成功的时候，则应该返回最后一个块*/
while(l<=r){
int mid=l+r>>1;
if(bv[mid].back()>=x){/*当前块满足了x*/
r=mid-1;/*前移一个块*/
re=mid;
}
else l=mid+1;/*整个块都无法满足x则后移一个块*/
}
return re;
}
inline void fit(int x){
sz=x;/*修改每块限制大小*/
}
inline void split(int x){
bv.emplace(bv.begin()+x+1,bv[x].begin()+sz/2,bv[x].end());/*在块x后新建一个块并插入x的后一半元素*/
bv[x].erase(bv[x].begin()+sz/2,bv[x].end());/*插入后删除块x的后一半*/
}
inline void merge(int x){
bv[x].insert(bv[x].end(),bv[x+1].begin(),bv[x+1].end());/*末尾添加下一个块的所有元素*/
bv.erase(bv.begin()+x+1);/*删除下一个块*/
}
inline void insert(int v){
if(bv.empty()){/*第一个元素*/
bv.emplace_back();/*创建一个新的vector*/
bv.back().emplace_back(v);/*添加元素*/
return;
}
int x=pos(v);/*找到元素所属块*/
bv[x].emplace(lower_bound(bv[x].begin(),bv[x].end(),v),v);/*二分找到位置并插入*/
if(bv[x].size()>sz)split(x);
}
inline void del(int v){
if(bv.empty())return;/*不存在元素则终止*/
int x=pos(v);
auto it=lower_bound(bv[x].begin(),bv[x].end(),v);
if(it==bv[x].end()||*it!=v)return;/*不存在v*/
bv[x].erase(it);
if(bv[x].empty()){
bv.erase(bv.begin()+x);/*整个块空了之后则删除该块*/
return;
}
if(bv.size()==1)return;
if(bv[x].size()<=sz/4){/*也可以不进行合并操作*/
if(x==0)merge(x);/*开头块则将自己和后面合并*/
else if(x==bv.size()-1)merge(x-1);/*末尾块则将自己和前面合并*/
else merge(x-(bv[x-1].size()<bv[x+1].size()));/*取size较小的一方进行合并*/
}
}
inline int rank(int v){
int x=pos(v),re=0;
for(int i=0;i<x;i++)re+=bv[i].size();/*累加小于v的数的个数*/
return lower_bound(bv[x].begin(),bv[x].end(),v)-bv[x].begin()+re+1;/*二分查找v在该块中的位置并返回小于x的数的个数+1*/
}
inline int kth(int k){
for(int i=0;i<bv.size();i++){
if(bv[i].size()>=k)return bv[i][k-1];/*找到第一个元素个数>=k的块*/
else k-=bv[i].size();/*更新k的值*/
}
return -1;
}
inline int pre(int v){
if(bv.empty()||bv[0][0]>=v)return -inf;/*空集或最小元素>=v则v没有前驱*/
int x=pos(v);
auto it=lower_bound(bv[x].begin(),bv[x].end(),v);/*首先在自己所在的块中寻找前驱*/
if(it==bv[x].begin())return bv[x-1].back();/*整块都>=v则返回上一个块的末尾元素，第一个判断已经保证了一定有解*/
else return *--it;/*返回前驱*/
}
inline int suc(int v){
if(bv.empty()||bv.back().back()<=v)return inf;
int x=pos(v);
auto it=upper_bound(bv[x].begin(),bv[x].end(),v);
if(it==bv[x].end())return bv[x+1][0];/*整块都<=v则返回下一个块的开头元素，第一个判断已经保证了一定有解*/
else return *it;/*返回后继*/
}
};