STL：rope
upd：rope 确实是
据说这个玩意其实是一开始只有 crope 的。因此其实他不是用来搞 OI 的。
关于 rope 的时间复杂度一直有争议，官方文档是描述为
声明
:::warning[测试]
使用学校机房，
结果
| 代码 | ||||
|---|---|---|---|---|
| Treap | ||||
| rope | 不想跑了 | |||
| 写假了的 AVL | - | - | - | |
| AVL | - | - | - | |
| BIT | - | - | - |
:::
注明：rope 在 CCF 的大多数赛事中可以使用，笔者已经亲身试毒。
基础用法
引用
#include<ext/rope>
using namespace __gnu_cxx;或者
#include<bits/extc++.h>
using namespace __gnu_cxx;定义
与 vector 类似，rope<type> 即可定义。
rope<type> rp(100000) 可以定义一个大小为
另外，rope<char> 可以写为 crope。
操作
这里只讲数组 rope 的使用方法。
在接下来的说明中，使用
a.push_back(x)：末尾插入x 。该操作为O(1) 。a.insert(p,x)：在pos 位置之后插入x 。注意 rope 是从0 开始的。a.erase(p,x)：从pos 位置向后删除x 个数。a.replace(x,y)：等价于a_x\gets y ，即单点修改。a.append(x)：同a.push_back(x)a.substr(p,x)：从pos 位置向后截取x 个数，并返回一个 rope。- rope 支持
clear()，empty()，begin()，end()，size()。 - rope 支持
for(auto i:a)格式的访问。
rope 强在哪里？
首先，rope 调用方法简单，比某 pbds 简单多了。
__gnu_pbds::tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>t;rope 是用来做可持久化的。因为 rope 的复制（即为 A=B，
开
你可以把它理解成一个可持久化的数组。
同样，把线段树的数组换为 rope 即可做可持久化线段树，但是不建议。谁愿意使用一个每次平衡都要开节点而且没有预分配空间的可持久化平衡树作为数组呢。
例题：P3919 【模板】可持久化线段树 1（可持久化数组）
例题：P1383 高级打字机
按照题意模拟即可。
| 对应的 rope 操作 | |
|---|---|
| Type | push_back |
| Undo | 回滚到 rp[x] |
| Query | rp[ver][x] |
例题：P3835 【模板】可持久化平衡树，你可以尝试拿到
题单：pbds 与 rope 的应用
以上还是简单的应用，接下来的可能有些玄学。
rope 的玄学运用（或许也是并查集的优化？）
例题：P3402 【模板】可持久化并查集
笔者翻阅了网上的资料，发现这篇文章的代码并不是在线的，并且会被卡掉。
:::info[资料代码]
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_cxx;
using namespace std;
const int N=2e5+5;
int f[N],r[N],n,m,op,a,b,cnt1,cnt2,cnt3;
struct node{
int op,a,b;
};
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*w;
}
int find(rope<int> &fa,int &i)
{
int f=fa[i];
return f==i?i:find(fa,f);
}
void merge(rope<int> &fa,int &a,int &b)
{
a=find(fa,a),b=find(fa,b);
if(a==b) return;
if(r[a]>r[b]) fa.replace(b,a);
else
{
if(r[a]==r[b]) r[b]++;
fa.replace(a,b);
}
}
void prework(){for(int i=1;i<=n;i++) f[i]=i;f[0]=1;}
vector<node> qus;
signed main()
{
qus.emplace_back((node){-1,-1,-1});
n=read(),m=read();
rope<int> fa[m+1];
prework();
fa[0]=rope<int>(f);
for(int i=1;i<=m;i++)
{
op=read();
if(op==1)
{
a=read(),b=read();
qus.emplace_back((node){op,a,b});
cnt1++;
}
else if(op==2) a=read(),cnt2++,qus.emplace_back((node){op,a,-1});
else
{
a=read(),b=read();
qus.emplace_back((node){op,a,b});
cnt3++;
}
}
if(cnt1>=99999&&cnt2<=3)
{
printf("0");
return 0;
}
for(int i=1;i<=m;i++)
{
op=qus[i].op;
if(op==1)
{
fa[i]=fa[i-1];
a=qus[i].a,b=qus[i].b;
merge(fa[i],a,b);
}
else if(op==2) a=qus[i].a,fa[i]=fa[a];
else
{
fa[i]=fa[i-1];
a=qus[i].a,b=qus[i].b;
printf("%d",(find(fa[i],a)==find(fa[i],b)?1:0));
putchar('\n');
}
}
}:::
同样，还有一篇题解的：
:::info[题解代码]
#include <bits/stdc++.h>
#include <ext/rope>
//#define int long long
#define endl '\n'
#define rint register unsigned
using namespace __gnu_cxx;
using namespace std;
#define IN stdin->_IO_read_ptr < stdin->_IO_read_end ? *stdin->_IO_read_ptr++ : __uflow(stdin)
#define OUT(_ch) stdout->_IO_write_ptr < stdout->_IO_write_end ? *stdout->_IO_write_ptr++ = _ch : __overflow(stdout, _ch)
const int N = 2e5 + 5;
unsigned f[N];
unsigned r[N];
void read(unsigned &x)
{
x = 0;
char ch = IN;
while (ch < 47)
ch = IN;
while (ch > 47)
x = (x << 1) + (x << 3) + (ch & 15), ch = IN;
}
unsigned find(rope<unsigned> &fa, unsigned &i)
{
unsigned f = fa[i];
return f == i ? i : find(fa, f);
}
void merge(rope<unsigned> &fa, unsigned &a, unsigned &b)
{
a = find(fa, a);
b = find(fa, b);
if (a == b)
{
return ;
}
if (r[a] > r[b])
{
fa.replace(b, a);
}
else
{
if (r[a] == r[b])
{
r[b]++;
}
fa.replace(a, b);
}
}
signed main()
{
unsigned n, m, op, a, b;
read(n);
read(m);
rope<unsigned> fa[m + 1];
for (rint i = 1; i <= n; i++)
{
f[i] = i;
}
f[0] = 1;
fa[0] = rope<unsigned>(f);
for (rint i = 1; i <= m; i++)
{
read(op);
switch (op)
{
case 1:
fa[i] = fa[i - 1];
read(a);
read(b);
merge(fa[i], a, b);
break;
case 2:
read(a);
fa[i] = fa[a];
break;
default:
fa[i] = fa[i - 1];
read(a);
read(b);
OUT(find(fa[i], a) == find(fa[i], b) ? '1' : '0');
puts("");
}
}
return 0;
}
:::
这写代码都使用了快读或离线特判等方式。
而笔者的呢？
PS：这个帖子其实是我发的，我被【】了。
:::info[代码]
#include<bits/extc++.h>
using namespace std;
const int maxn=5e5+10;
int rk[maxn],T;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*w;
}
int opt1,opt2,opt3;
struct DSU{
int ver=0;
__gnu_cxx::rope<int> fa[maxn];
void reset(int v,int n){
fa[v].push_back(1);
for(int i=1;i<n;i++)fa[v].push_back(i),rk[i]=1;
}
int find(int x){
if(fa[ver][x]==x)return x;
if(rand()%T==0)fa[ver].replace(x,find(fa[ver][x]));
return find(fa[ver][x]);
}
void merge(int x,int y){
ver++;
fa[ver]=fa[ver-1];
int fx=find(x),fy=find(y);
if(fx==fy)return;
//fa[fx]=fy
if(rk[fx]<=rk[fy])fa[ver].replace(fx,fy);
else fa[ver].replace(fy,fx);
if(rk[fx]==rk[fy]&&fx!=fy)rk[fy]++;
}
void back(int v){
ver++;
fa[ver]=fa[v];
}
bool group(int a,int b){
ver++;
fa[ver]=fa[ver-1];
return find(a)==find(b);
}
};
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
int n,m;
n=read(),m=read();
DSU d;
T=sqrt(n)*log2(n);
d.reset(0,n+1);
while(m--){
int opt;
opt=read();
if(opt==1){
int a,b;
a=read(),b=read();
d.merge(a,b);
}
else if(opt==2){
int k;
k=read();
d.back(k);
}
else{
int a,b;
a=read(),b=read();
putchar(d.group(a,b)^48);
putchar('\n');
}
}
return 0;
} :::