本题链接：登录—专业IT笔试面试备考平台_牛客网
题目：
样例1：
|
| 2 3 4 1 5 |
样例2：
|
| 3 4 1 2 5 |
样例3：
|
| 3 4 1 5 2 |
思路：
这道题，其实就是个模拟题，根据题意。
第一行输入，n 为排列数 1~n，初始为递增序列，m 为操作次数。
随后 m 行，第一个数是 下标pos，第二个数是 长度 len。
每次切割以下标 pos 做起点到长度len 的数组拿取出来，放到前面，，问操作后的最终序列。
根据这题意，尝试模拟一遍，截取长度数组方面，有一个办法是将它们当作string进行截取删除放置操作。
模拟代码如下：
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();signed main()
{
// freopen("a.txt", "r", stdin);IOS;int _t = 1;// cin >> _t;while (_t--){solve();}return 0;
}
string s;
int n,m;// 初始化序列
inline void Init()
{for(int i = 1;i <= n;++i){s += char(i + '0');}
}inline void Print_ans()
{for(int i = 0;i < s.size();++i){if(i) cout << ' ';cout << s[i];}
}
inline void solve()
{cin >> n >> m;Init();while(m--){int pos,len;cin >> pos >> len;pos -= 1; // 我们的 s 下标是以 0 开始，所以这里 -1string tem = s.substr(pos,len); // 拿取这个区间的序列s.erase(pos,len); // 删除以 pos作为起点，长度为len的序列s = tem + s;}// 输出答案Print_ans();
}提交后：
不出意料，超时了，这种明明是模拟题却出现超时的结果，这种情况就是需要一些特殊的数据结构了。
而这种结构之一，我们可以使用平衡树写法，平衡树的操作大部分都是 O(log n) 时间复杂度，而我们上面的代码string的操作时间复杂度是 O(n),所以很容易出现超时的现象。
那么根据平衡树，手写的话会很麻烦，其实，C++STL库中也内置了平衡树的操作，我们可以调用。具体操作如下：
rope平衡树具体操作：
#include<ext/rope>///头文件
using namespace __gnu_cxx;
rope <int> tree;
int main(){int x = 2;tree.push_back(x); //在末尾加xtree.insert(pos, x); //在pos位置加入xtree.erase(pos, len); //从pos位置删除len个元素tree.copy(pos, len, x); //从pos开始len个元素用x代替tree.replace(pos, x); //从pos开始全部换为xtree.substr(pos, len); //提取pos开始len个元素tree.at(i);tree[i]; //访问第x个元素return 0;
}
并且rope< int>相当于一个块状链表。可以用substr等函数实现区间处理。
如果是rope< char>，相当于一个重型string。可以cout；可以+=。
rope最大的特点是支持可持久化。rope可以o(1)继承上一个版本。（内部维护了平衡树的指针）
最后要注意引用rope的细节：
#include <ext/rope>
using namespace __gnu_cxx;代码详解如下：
#include <iostream>
#include <ext/rope>
#define endl '\n'
#define int long long
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
using namespace __gnu_cxx;
const int N = 2e6 + 10;
inline void solve();signed main()
{
// freopen("a.txt", "r", stdin);IOS;int _t = 1;// cin >> _t;while (_t--){solve();}return 0;
}int n,m;
rope<int>tree; // 平衡树存值
// 初始化序列
inline void Init()
{for(int i = 1;i <= n;++i) tree.push_back(i);
}// 输出答案
inline void Print_ans()
{for(int i = 0;i < (int)tree.size();++i){if(i) cout << ' ';cout << tree[i];}
}
inline void solve()
{cin >> n >> m;Init();while(m--){int pos,len;cin >> pos >> len;pos -= 1; // 下标是以 0 开始，所以这里需要 -1rope<int> tem = tree.substr(pos,len); // 截取区间序列tree.erase(pos,len); // 删除区间序列，缩进序列tree = tem + tree; // 放置前面}// 输出答案Print_ans();
}
