#include<ext/rope> //包含头
typedef __gnu_cxx::rope<int> rp; //名称空间
/*
rope可以实现
1.可持久化数组
2.高效区间翻转
操作
test.push_back(x);//在末尾添加x
test.insert(pos,x);//在pos插入x
test.erase(pos,x);//从pos开始删除x个
test.copy(pos,len,x);//从pos开始到pos+len为止用x代替
test.replace(pos,x);//将pos换成x
test.substr(pos,x);//提取pos开始x个
test.at(x)/[x];//访问第x个元素
算法复杂度n*sqrt(n)可以实现快速的插入、删除和查找
*/
//1.可持久化并查集
int find(int x,rp *ver) {
if(x==ver->at(x))return x;
int t=find(ver->at(x),ver);
if(t!=ver->at(x))ver->replace(x,t);
return ver->at(x);
}
void merge(int x,int y,rp*ver){
x=find(x,ver),y=find(y,ver);
if(x!=y)ver->replace(x,y);
}
int main() {
n=read(),m=read();
rp **V=new rp*[n+3];
V[0]=new rp();
for(int i=0; i<=n; i++)V[0]->push_back(i);
for(int i=1; i<=m; i++) {
V[i]=new rp(*V[i-1]);//一定注意这里是new老节点
int o=read();
if(o==1)merge(read(),read(),V[i]);
else if(o==2)V[i]=new rp(*V[read()]);
else puts(find(read(),V[i])==find(read(),V[i])?"1":"0");
}
return 0;
}
//2.区间翻转
void rev(int r,int l) {
if(l>r)std::swap(l,r);
r++;
rop tmp=s.substr(s.begin()+l,s.begin()+r);
s=s.substr(s.begin(),s.begin()+l)+rs.substr(rs.begin()+n-r,rs.begin()+n-l)+s.substr(s.begin()+r,s.end());
rs=rs.substr(rs.begin(),n-r+rs.begin())+tmp+rs.substr(n - l + rs.begin(),rs.end());
}
int main() {
n=read(),m=read();
for(int i=1; i<=n; i++)s.append(i),rs.append(n-i+1);
while(m--)rev(read()-1,read()-1);
for(int i=0; i<n; i++)printf("%d ",s.at(i));
return 0;
}
/*
注意到STL的begin及end为左闭右开 r++
反转区间时 l r均--
*/
Categories:
Tags:
No responses yet