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;
}
平衡树套平衡树
P8306 【模板】字典树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
AC不了，常数巨大
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
char buffer[3000005];
signed main(){
int T = read();
while(T--){
__gnu_pbds::trie<string, __gnu_pbds::null_type, __gnu_pbds::trie_string_access_traits<>,
__gnu_pbds::pat_trie_tag, __gnu_pbds::trie_prefix_search_node_update> trie;
int n = read(), q = read();
for(int i = 1; i <= n; i++){
scanf("%s", buffer);
trie.insert(string(buffer));
}
while(q--){
int ans = 0;
scanf("%s", buffer);
auto range = trie.prefix_range(string(buffer));
for(auto it = range.first; it != range.second; it++) ans++;
printf("%d\n", ans);
}
}
return 0;
}
标签：pbds,下标,int,rbt,tree,pos,rope,应用 From： https://www.cnblogs.com/mingloch/p/17564175.html