星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P3369 【【模板】普通平衡树(Treap/SBT)】

posted on 2017-07-26 23:19:55 | under 题解 |

声明:最好是有一定平衡树基础的同学再来看这个题解,你首先得会手写:D

这里向大家介绍一个神奇的宝贝:pb_ds库的tree。

tree的功能相当强大,而这一题就可以用到里面封装的平衡树。

我尝试了Splay和红黑树(红黑树用的别人的代码),发现果然RBT快了不少,Splay耗时接近RBT的三倍了。

使用pb_ds,背代码的能力必不可少,比如用tree就需要两个很长的头文件,具体参考代码。

但是需要注意的是,由于这个模板的erase只需要删除一个数,因此我们需要对插入的数进行简单的处理虽然这个“简单的”处理和奇特的处理lowerbound耗费了我一两个小时才写完,我觉得我智商也是没救了

关于pb_ds的详细内容见代码吧。当然,建议还是去网上找博客详细深挖。

最后,我爱pb_ds,我爱STL。

#include<cstdio>
#include<iostream>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>//头文件
#define f(i,a,b) for(i=a;i<=b;++i)
using namespace  __gnu_pbds;//由于定义tree时逐个添上这个东西太难缠了,于是干脆就这样了
typedef long long ll;
tree<ll,null_type,std::less<ll>,splay_tree_tag,tree_order_statistics_node_update>st;//splay,只要把splay改为rb就是红黑树XD,另外注意std::less
int main()
{
    int i,j,m;
    ll ans,x,y;
    scanf("%d",&m);
    f(i,1,m)
    {
        scanf("%lld%lld",&x,&y);
        if(x==1)st.insert((y<<20)+i);//简单的处理
        else if(x==2)st.erase(st.lower_bound(y<<20));
        else if(x==3)printf("%d\n",st.order_of_key(y<<20)+1);
        else
        {
            if(x==4)ans=*st.find_by_order(y-1);
            if(x==5)ans=*--st.lower_bound(y<<20);
            if(x==6)ans=*st.lower_bound((y+1)<<20);
            printf("%lld\n",ans>>20);//一并处理ans
        }
    }//f(i,0,st.size()-1)printf("%lld ",(*st.find_by_order(i))>>20);//check
    return 0;
}