rope 块状链表实现的STL容器

(Updated: )
(3 mins to read)

crope = rope（可以直接cin cout）

1
2
#include <ext/rope>
using namespace __gnu_cxx;

可以较快速的解决区间移动、区间插入删除、区间翻转问题

1
2
3
4
5
6
7
8
9
10
11
rp.push_back(x); // 在末尾插入 x
rp.insert(pos, x); // 从pos 处插入一个数组x
rp.erase(pos, x); // 从pos 处删除 x 个元素
rp.length(); // 返回 rp 的大小
rp.size(); // 同上
rp.replace(pos, x); // 将 pos 处的元素替换成 x
rp.substr(pos, x); // 从 pos 处开始提取 x 个元素
rp.copy(pos, x, s); // 从 pos 处开始复制 x 个元素到 s(string or char*(末尾要手动加0)) 中
rp[x]; // 访问第 x 个元素
rp.at(x); // 同上
operator.+() //拼接操作，很快速
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
rope<int>s;
int main()
{
  int n,m,k,l;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i)s.push_back(i);
  while(m--)
  {
    scanf("%d%d",&l,&k);
    s=s.substr(l-1,k)+s.substr(0,l-1)+s.substr(l+k-1,n+1-k-l);
  }
  for(auto c:s)
    printf("%d ",c);
  puts("");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
rope<int>a;
int main(){
  int n,m,x,y;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    a.push_back(i);
  }
  for(int i=0;i<m;i++){
    cin>>x>>y;
    a.insert(0,a.substr(x-1,y));
    a.erase(x+y-1,y);
  }
  for(int i=0;i<n;i++){
    if(i==0){
      cout<<a[i];
    }else{
      cout<<" "<<a[i];
    }
  }
  cout<<endl;
}