pbds的應(yīng)用
pbds大法好
頭文件及命名空間
#include<bits/extc++.h> using namespace __gnu_pbds;
調(diào)用
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) //插入一個數(shù) x
T.erase(x) //刪除一個數(shù) x，如果沒有這個數(shù)，那么什么都不會做
T.order_of_key(x) //查詢一個數(shù) x 的排名,返回比這個數(shù)小的數(shù)的個數(shù)，即使原樹中沒有這個數(shù)也可以查詢
*T.find_by_order(x-1) //查詢排名為 x 的數(shù),
由于返回的是迭代器(和指針差不多的用途)，所以要用 * 來獲取地址所存的值，
并且 tree 里面的排名是從零開始的，所以要查排名為 x-1 的數(shù)的值
*T.lower_bound(x)查找第一個大于等于 x 的數(shù)，返回的也是迭代器,并且即使原樹中沒有 x 也可以查找
當(dāng)然前提是這個tree的類型是less<int>
如果類型是greater<int>,查找的就是第一個小于等于 x 的數(shù)
*T.upper_bound(x)查找第一個大于/小于 x 的數(shù)，同上
T.join(b) b并入T 前提是兩棵樹的key的取值范圍不相交,即兩棵樹里面沒有相同的數(shù)
T.split(v,b) 小于等于v的元素屬于T，其余的屬于b
需要注意的是tree會自動去重，
所以如果要使它里面存多個相同的數(shù)，就需要一點(diǎn)投機(jī)取巧的方法
P6136 【模板】普通平衡樹（數(shù)據(jù)加強(qiáng)版） - 洛谷 | 計算機(jī)科學(xué)教育新生態(tài) (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 【模板】普通平衡樹 - 洛谷 | 計算機(jī)科學(xué)教育新生態(tài) (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大法好，可持久化數(shù)據(jù)沒煩惱）
P3391 【模板】文藝平衡樹 - 洛谷 | 計算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
頭文件及命名空間
#include<bits/stdc++.h> #include<ext/rope> using namespace std; using namespace __gnu_cxx;
調(diào)用
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個變量。
區(qū)間反轉(zhuǎn)
其實(shí)非常簡單，只要使用兩個rope，一個正著建立，一個反向建立，然后通過具體的插入操作實(shí)現(xiàn)就可以了
具體操作
如果你把rope定義為string：
insert(int pos, string &s, int n) 將字符串s的前n位插入rope的下標(biāo)pos處，如沒有參數(shù)n則將字符串s的所有位都插入rope的下標(biāo)pos處 （補(bǔ)充地址知識：如果你不想從字符串下標(biāo)為0（即第一個字符）的地址開始取 n位，就將你想開始取的地址代入。如s+1表示從字符串下標(biāo)為1（即第二個字符）的地址開始取n位。int、char等變量類型的數(shù)組都適用這種方法來更改數(shù)組操作的起始位置。）
append(string &s,int pos,int n) 把字符串s中從下標(biāo)pos開始的n個字符連接到rope的結(jié)尾，如沒有參數(shù)n則把字符串s中下標(biāo)pos后的所有字符連接到rope的結(jié)尾，如沒有參數(shù)pos則把整個字符串s連接到rope的結(jié)尾（這里已經(jīng)給你起始位置參數(shù)pos了就沒必要用上述的取地址方法了哈）
（insert和append的區(qū)別：insert能把字符串插入到rope中間，但append只能把字符串接到結(jié)尾）
substr(int pos, int len) 提取rope的從下標(biāo)pos開始的len個字符
at(int x) 訪問rope的下標(biāo)為x的元素
erase(int pos, int num) 從rope的下標(biāo)pos開始刪除num個字符
copy(int pos, int len, string &s) 從rope的下標(biāo)pos開始的len個字符用字符串s代替，如果pos后的位數(shù)不夠就補(bǔ)足
replace(int pos, string &x);//從rope的下標(biāo)pos開始替換成字符串x，x的長度為從pos開始替換的位數(shù)，如果pos后的位數(shù)不夠就補(bǔ)足
以上是常用操作，不常用操作這里就不再贅述。
如果你把rope定義為int（這里只是以int為例）：
insert(int pos, int *s, int n) 將int數(shù)組（以下的s都是int數(shù)組）s的前n位插入rope的下標(biāo)pos處，如沒有參數(shù)n則將數(shù)組s的所有位都插入rope的下標(biāo)pos處
append(int *s,int pos,int n) 把數(shù)組s中從下標(biāo)pos開始的n個數(shù)連接到rope的結(jié)尾，如沒有參數(shù)n則把數(shù)組s中下標(biāo)pos后的所有數(shù)連接到rope的結(jié)尾，如沒有參數(shù)pos則把整個數(shù)組s連接到rope的結(jié)尾
substr(int pos, int len) 提取rope的從下標(biāo)pos開始的len個數(shù)
at(int x) 訪問rope的下標(biāo)為x的元素
erase(int pos, int num) 從rope的下標(biāo)pos開始刪除num個數(shù)
copy(int pos, int len, int *s) 從rope的下標(biāo)pos開始的len個數(shù)用數(shù)組s代替，如果pos后的位數(shù)不夠就補(bǔ)足
replace(int pos, int *x);//從rope的下標(biāo)pos開始替換成數(shù)組x，x的長度為從pos開始替換的位數(shù)，如果pos后的位數(shù)不夠就補(bǔ)足
文藝平衡樹代碼
#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 【模板】二逼平衡樹（樹套樹） - 洛谷 | 計算機(jī)科學(xué)教育新生態(tài) (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 【模板】字典樹 - 洛谷 | 計算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
AC不了，常數(shù)巨大
#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; }
P3377 【模板】左偏樹（可并堆） - 洛谷 | 計算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
優(yōu)先隊列 priority_queue 貌似在stl里？
但是
pbds庫里也提供了優(yōu)先隊列 并且還提供了合并操作和修改元素操作
頭文件
#include<bits/stdc++.h>
#include<bits/extc++.h>
命名空間
using namespace std; using namespace __gnu_pbds;
調(diào)用
__gnu_pbds::priority_queue<變量類型，比較方式>變量名[堆的個數(shù)]
具體操作
push操作 將一個元素壓入隊列
pop操作 將隊頂元素彈出隊列
top操作 得到對頂元素
size操作 返回隊列元素個數(shù)
clear操作 清空隊列所有元素
empty操作 返回隊列是否為空
join操作 合并兩個堆
modify操作 修改一個位置的值，并且自動調(diào)整堆的結(jié)構(gòu)
erase操作 刪除某個位置的元素
具體代碼實(shí)現(xiàn)左偏樹
#include<bits/stdc++.h> #include<bits/extc++.h> using namespace std; #define ll long long const int N=1e5+5; __gnu_pbds::priority_queue<pair<ll,ll>,greater<pair<ll,ll> > >heaps[N]; ll n,m,fa[N]; bool deletes[N]; ll find(ll x) { return fa[x]==x?x:fa[x]=find(fa[x]); } int main() { //freopen("P3377.in","r",stdin); //freopen("P3377.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) { ll x; fa[i]=i; deletes[i]=false; cin>>x; heaps[i].push(make_pair(x,i)); } for(int i=1;i<=m;i++) { ll op,x,y,fax,fay; cin>>op; if(op==1) { cin>>x>>y; fax=find(x); fay=find(y); if(fax==fay||deletes[x]||deletes[y]) continue; if(heaps[fax].size()>=heaps[fay].size()) { fa[fay]=fax; heaps[fax].join(heaps[fay]); } else { fa[fax]=fay; heaps[fay].join(heaps[fax]); } } else { cin>>x; if(deletes[x]) { cout<<"-1"<<endl; continue; } fax=find(x); pair<ll,ll>opj; opj=heaps[fax].top(); cout<<opj.first<<endl; deletes[opj.second]=true; heaps[fax].pop(); } } return 0; }
浙公網(wǎng)安備 33010602011771號