STL rope
rope的时间复杂度
查询复杂度是P(N½),插入复杂度是P(N½),空间复杂度是O(N)。
rope初始用法
初始的rope存放的类型是string。
- insert(int pos,string &s,int n) 把字符串s中的前n位插入rope下标pos处。
- append(string &s,int pos,int n)把字符串s中从下标pos开始的n个字符连接到rope的结尾
- substr(int pos,int len)
提取rope的从下标pos开始的len个字符
- 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后的位数不够就补足。
所以这个不是少了一个参数的copy吗?
rope的常用用法
雾
rope存放的类型大多是int.
- insert(int pos,int *s,int n) 把s中的前n位插入rope下标pos处。
- append(int *s,int pos,int n)把字符串s中从下标pos开始的n个字符连接到rope的结尾
- substr(int pos,int len)
提取rope的从下标pos开始的len个数
- 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后的位数不够就补足。
所以这个不是少了一个参数的copy吗?
当然,它有size()
注意事项
使用时要加#include<ext/rope>
using namespace __gnu_cxx;
例题
给道例题
#include <ext/rope>
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_cxx;
rope<int> S;
void solve() {
int n, q;
cin >> n >> q;
S.clear();
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
S.push_back(t);
}
int ans = 0;
while (q--) {
int op, l, r, x;
cin >> op;
if (op == 1) {
cin >> l >> r;
S = S.substr(0, r) + S.substr(l - 1, n - r);
} else {
cin >> x;
cout << S[x - 1] << endl;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
标签:下标,string,int,pos,介绍,rope,len
From: https://www.cnblogs.com/zychh/p/16910243.html