简易平衡树

Vector的下标和数组一样从0开始的

(vector<int>vec)

(vec.size();) //返回向量的实际大小

$vec.begin(); $//返回向量的开始指针的位置

(vec.end();) //返回向量的结束指针的下一个位置

(vec.push\_back(x);) //在对象末尾插入数据x

(vec.pop\_back();) //在对象末尾删除数据

(vec.clear();) //清除对象中的所有数据

(vec.at(i);) //访问容器中第i个数的值或(vec[i])

在第(i+1)个数前面插入一个数(x:vec.insert(vec.begin()+i,x))

删除第(i+1)个数(:vec.erase(vec.begin()+i))

#include<algorithm>
lower_bound(); upper_bound(); unique();//判重
lower_bound(a + 1,a + n + 1,x);//在begin到end-1二分查找有序表中第一个大于等于x的数的位置
//仅适用于非降序的有序表，如果是非升序的有序表，则需要重载：
lower_bound(a+1,a+n+1,x,greater<int>());
int t=lower_bound(a+1,a+n+1,x)-a;//在begin到end-1查找第一个大于等于x的数的位置，返回值是地址 if(a[t]==x) //如果这个数==x
printf("%d
",t);
upper_bound(a+1,a+n+1,x)-a;//二分查找有序表中第一个大于x的数的位置,仅适用于非降序的有序表
int k=unique(a+1,a+n+1)-a;//得到有效长度,去重
for(int i=1;i<=k;i++) //只输出有效长度
printf("%d ",a[i]);

P3369普通平衡树

操作：插入(x)，删除(x)，查询(x)排名(()比当前小的数(+1))，查询排名(x)数，(x)前驱((小于x且最大))，(x)后继((大于x，且最小))

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>v;
int n,opt,x;
int main()
{
    v.reserve(100001);
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&opt,&x);
        if(opt==1)    v.insert(lower_bound(v.begin(),v.end(),x),x);
        if(opt==2)    v.erase (lower_bound(v.begin(),v.end(),x));
        if(opt==3)    printf("%d
",lower_bound(v.begin(),v.end(),x)-v.begin()+1);
        if(opt==4)    printf("%d
",v[x-1]);
        if(opt==5)    printf("%d
",v[lower_bound(v.begin(),v.end(),x)-v.begin()-1]);
        if(opt==6)    printf("%d
",v[upper_bound(v.begin(),v.end(),x)-v.begin()]);
    }
    return 0;
}

(P1801)

有一整数数组，初始为空，一特殊变量，初始为(0)。(add(x))，把(x)加入数组。(get(x):在x次add后，++i)，输出数组中第(i)小的数

小根堆当黑匣子，加入数据，大根堆(get)操作，把任务交给大根堆，堆顶传递给大根堆，大根堆存着堆中最小的(i)个数，继续读(a)，如果(a)比大根堆堆顶还大，把它扔进小根堆，如果小，(a)属于数组前(i)小，大根堆堆顶没有存在它的意义，回到小根堆，在线解决问题

m=read(),n=read();
    for(int i=1;i<=m;i++)a[i]=read();
    for(int i=1;i<=n;i++)
    {
        u=read();
        while(cnt<u)
        {
            ++cnt;
            if(!p.empty()&&a[cnt]<p.top())//一定要判空，否则RE等着你。
            {
                q.push(-p.top());
                p.pop();
                p.push(a[cnt]);
            }
            else q.push(-a[cnt]);//直接加入小根堆。
        }
        printf("%lld
",-q.top());
        p.push(-q.top());
        q.pop();
    }