526互联

pbds的应用

发布时间 2023-07-18 21:27:22作者: Noname_min

pbds大法好

头文件及命名空间

#include<bits/extc++.h>
using namespace __gnu_pbds;

调用

tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update>rbt;
tree<pair<int,int>,null_type,less<pair<int,int> >,splay_tree_tag,tree_order_statistics_node_update>rbt;

具体用法

T.insert(x) //插入一个数 x

T.erase(x) //删除一个数 x，如果没有这个数，那么什么都不会做

T.order_of_key(x) //查询一个数 x 的排名,返回比这个数小的数的个数，即使原树中没有这个数也可以查询

*T.find_by_order(x-1) //查询排名为 x 的数,

由于返回的是迭代器(和指针差不多的用途)，所以要用 * 来获取地址所存的值，

并且 tree 里面的排名是从零开始的，所以要查排名为 x-1 的数的值

*T.lower_bound(x)查找第一个大于等于 x 的数，返回的也是迭代器,并且即使原树中没有 x 也可以查找

当然前提是这个tree的类型是less<int>

如果类型是greater<int>,查找的就是第一个小于等于 x 的数

*T.upper_bound(x)查找第一个大于/小于 x 的数，同上

T.join(b) b并入T 前提是两棵树的key的取值范围不相交,即两棵树里面没有相同的数

T.split(v,b) 小于等于v的元素属于T，其余的属于b

需要注意的是tree会自动去重，

所以如果要使它里面存多个相同的数，就需要一点投机取巧的方法

P6136 【模板】普通平衡树（数据加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update>rbt;
int n,m,cnt,ans,last;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        rbt.insert(make_pair(x,++cnt));
    }
    for(int i=1;i<=m;i++)
    {
        int op,x;
        cin>>op>>x;
        x^=last;
        if(op==1)
        {
            rbt.insert(make_pair(x,cnt++));
        }
        if(op==2)
        {
            auto it=rbt.lower_bound(make_pair(x,0));
            rbt.erase(it);
        }
        if(op==3)
        {
            last=rbt.order_of_key(make_pair(x,0))+1;
        }
        if(op==4)
        {
            last=rbt.find_by_order(x-1)->first;
        }
        if(op==5)
        {
            last=rbt.find_by_order(rbt.order_of_key(make_pair(x,0))-1)->first;
        }
        if(op==6)
        {
            last=rbt.find_by_order(rbt.order_of_key(make_pair(x,2147483647)))->first;
        }
        if(op>2)
            ans^=last;
    }
    cout<<ans;
    return 0;
}

P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
const int N=100005;
int ans,flag;
cc_hash_table<int,int>f;
tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update>rbt;
int main()
{
    //freopen("pbds.in","r",stdin);
    //freopen("pbds.out","w",stdout);
    ios::sync_with_stdio(0);
    int n,op,x;
    cin>>n;
    while(n--)
    {
        cin>>op>>x;
        if(op==1) rbt.insert(make_pair(x,++f[x]));
        if(op==2) rbt.erase(make_pair(x,f[x]--));
        if(op==3) cout<<(rbt.order_of_key(make_pair(x,1))+1)<<endl;
        if(op==4) cout<<(rbt.find_by_order(x-1)->first)<<endl;
        if(op==5) cout<<(rbt.find_by_order(rbt.order_of_key(make_pair(x,0))-1))->first<<endl;
        if(op==6) cout<<(rbt.upper_bound(make_pair(x,10000000000)))->first<<endl;
    }
    return 0;
}

这就完了吗

不不不

pbds封装了一个非常好用的东西

rope（rope大法好，可持久化数据没烦恼）

P3391 【模板】文艺平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

头文件及命名空间

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;

调用

rope<类型>变量名

操作

R.push_back(a) //往后插入
R.insert(pos,a)//在pos位置插入a，pos是一个迭代器。
R.erase(pos,n)//在pos位置删除n个元素。
R.replace(pos,x)//从pos开始替换成x
R.substr(pos,x)//从pos开始提取x个变量。

 区间反转

其实非常简单，只要使用两个rope，一个正着建立，一个反向建立，然后通过具体的插入操作实现就可以了

具体操作

如果你把rope定义为string：

　　　　insert(int pos, string &s, int n) 将字符串s的前n位插入rope的下标pos处，如没有参数n则将字符串s的所有位都插入rope的下标pos处 （补充地址知识：如果你不想从字符串下标为0（即第一个字符）的地址开始取n位，就将你想开始取的地址代入。如s+1表示从字符串下标为1（即第二个字符）的地址开始取n位。int、char等变量类型的数组都适用这种方法来更改数组操作的起始位置。）

  append(string &s,int pos,int n) 把字符串s中从下标pos开始的n个字符连接到rope的结尾，如没有参数n则把字符串s中下标pos后的所有字符连接到rope的结尾，如没有参数pos则把整个字符串s连接到rope的结尾（这里已经给你起始位置参数pos了就没必要用上述的取地址方法了哈）

　　　　（insert和append的区别：insert能把字符串插入到rope中间，但append只能把字符串接到结尾）

 

　　　　substr(int pos, int len) 提取rope的从下标pos开始的len个字符

 

　　　　  at(int x) 访问rope的下标为x的元素

　　　　

　　　　erase(int pos, int num) 从rope的下标pos开始删除num个字符

 

　　　　copy(int pos, int len, string &s) 从rope的下标pos开始的len个字符用字符串s代替，如果pos后的位数不够就补足

 

　　　　  replace(int pos, string &x);//从rope的下标pos开始替换成字符串x，x的长度为从pos开始替换的位数，如果pos后的位数不够就补足

 

　　　　以上是常用操作，不常用操作这里就不再赘述。

 

　   ●如果你把rope定义为int（这里只是以int为例）：

　　　  insert(int pos, int *s, int n) 将int数组（以下的s都是int数组）s的前n位插入rope的下标pos处，如没有参数n则将数组s的所有位都插入rope的下标pos处

 

　　　　append(int *s,int pos,int n) 把数组s中从下标pos开始的n个数连接到rope的结尾，如没有参数n则把数组s中下标pos后的所有数连接到rope的结尾，如没有参数pos则把整个数组s连接到rope的结尾

 

　　　　  substr(int pos, int len) 提取rope的从下标pos开始的len个数

 

　　　　at(int x) 访问rope的下标为x的元素

　　　　

　　　　erase(int pos, int num) 从rope的下标pos开始删除num个数

 

　　　　copy(int pos, int len, int *s) 从rope的下标pos开始的len个数用数组s代替，如果pos后的位数不够就补足

 

　　　   replace(int pos, int *x);//从rope的下标pos开始替换成数组x，x的长度为从pos开始替换的位数，如果pos后的位数不够就补足

文艺平衡树代码

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
int n,m;
int l,r;
rope<int> rpp,rpn;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    rpp.push_back(0),rpn.push_back(0);
    for(int i=1;i<=n;++i)
        rpp.push_back(i),rpn.push_back(n-i+1);
    while(m--)
    {
        cin>>l>>r;
        rpp.insert(r+1,rpn.substr(n-r+1,r-l+1)),
        rpn.insert(n-l+2,rpp.substr(l,r-l+1));
        rpp.erase(l,r-l+1),rpn.erase(n-r+1,r-l+1);
    }
    for(int i=1;i<=n;++i) printf("%d ",rpp[i]);
    return 0;
}

附二逼平衡树代码

P3380 【模板】二逼平衡树（树套树） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int INF=100000000,N=3e6+5;;
int n,m,a[N],tot,rt,lch[N],rch[N];
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>tr[N];
void insert(int& p,int l,int r,int k,int pos,bool op)
{
    if(!p)p=++tot;
    if(op)tr[p].insert(pos);
    else tr[p].erase(pos);
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(k<=mid)insert(lch[p],l,mid,k,pos,op);
    else insert(rch[p],mid+1,r,k,pos,op);
}
int getrank(int& p,int l,int r,int k,int ql,int qr)
{
    if(!p)p=++tot;
    if(r<=k)return tr[p].order_of_key(qr+1)-tr[p].order_of_key(ql);
    int mid=(l+r)>>1,ans=getrank(lch[p],l,mid,k,ql,qr);
    if(k>mid)ans+=getrank(rch[p],mid+1,r,k,ql,qr);
    return ans;
}
int kth(int& p,int l,int r,int k,int ql,int qr)
{
    if(!p)p=++tot;
    if(l==r)return l;
    int mid=(l+r)>>1;
    int cnt=tr[lch[p]].order_of_key(qr+1)-tr[lch[p]].order_of_key(ql);
    if(cnt>=k)return kth(lch[p],l,mid,k,ql,qr);
    else return kth(rch[p],mid+1,r,k-cnt,ql,qr);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)insert(rt,0,INF,a[i],i,1);
    for(int i=1;i<=m;i++)
    {
        int op,l,r,pos,k;
        scanf("%d",&op);
        if(op!=3)
            scanf("%d%d",&l,&r);
        else scanf("%d",&pos);
        scanf("%d",&k);
        if(op==1)    printf("%d\n",getrank(rt,0,INF,k-1,l,r)+1);
        else if(op==2)    printf("%d\n",kth(rt,0,INF,k,l,r));
        else if(op==3)
        {
            insert(rt,0,INF,a[pos],pos,0);
            insert(rt,0,INF,a[pos]=k,pos,1);
        }
        else if(op==4)
        {
            int rk=getrank(rt,0,INF,k-1,l,r)+1;
            if(rk==1) printf("-2147483647\n");
            else printf("%d\n",kth(rt,0,INF,rk-1,l,r));
        }
        else
        {
            int rk=getrank(rt,0,INF,k,l,r)+1;
            if(rk>r-l+1) printf("2147483647\n");
            else printf("%d\n",kth(rt,0,INF,rk,l,r));
        }
    }
    return 0;
}

平衡树套平衡树