链接：
https://www.nowcoder.com/acm/contest/141/C
题意：
给出一个n个元素的序列（1,2,...,n）和m个操作（1≤n,m≤1e5），
每个操作给出两个数p和s（1≤pi≤n，1≤si≤n-pi+1），表示把序列中从p开始的s个数移到最前面，
例如序列[1,2,3,4,5]在p=2，s=3时变成序列[2,3,4,1,5]，输出最后的序列。
分析：
对于每个操作，直接把序列拆成三个部分，再重新拼接一下就行。
可以用Splay或rope来快速完成这个操作。
代码：
Splay版
#include <cstdio> /// 元素编号从1开始，使用前要初始化（init）
template<typename type> // 元素类型
class SplaySequence {
public:
struct Node {
Node *ch[]; // 左右子树
int s; // 结点数
type v; // 值
bool flip; // 反转标记
int cmp(int k) const {
int d = k - ch[]->s;
if(d == ) return -;
return d <= ? : ;
}
void maintain() {
s = ch[]->s + ch[]->s + ;
}
void pushdown() {
if(!flip) return;
flip = false;
Node* t = ch[]; ch[] = ch[]; ch[] = t;
ch[]->flip ^= ;
ch[]->flip ^= ;
}
};
Node* root; // 根结点
// 将序列分裂成s[1...k]和s[k+1...o->s]，分别放于left和right
void split(Node* o, int k, Node* &left, Node* &right) {
if(k <= ) {
left = null;
right = o;
return;
}
splay(o, k);
left = o;
right = o->ch[];
o->ch[] = null;
left->maintain();
}
// 合并left和right。
Node* merge(Node* left, Node* right) {
if(left == null) return right;
splay(left, left->s);
left->ch[] = right;
left->maintain();
return left;
}
// 在第k个元素之后插入v
void insert(int k, type v) {
Node *left, *right, *mid = newNode();
mid->ch[] = mid->ch[] = null;
mid->s = ;
mid->v = v;
mid->flip = false;
split(root, k, left, right);
root = merge(merge(left, mid), right);
}
// 删除第k个元素
void erase(int k) {
Node *left, *right, *mid, *o;
split(root, k-, left, o);
split(o, , mid, right);
root = merge(left, right);
delNode(mid);
}
// 将第L...R个元素反转
void reverse(int L, int R) {
Node *left, *right, *mid, *o;
split(root, L-, left, o);
split(o, R-L+, mid, right);
mid->flip ^= ;
root = merge(merge(left, mid), right);
}
// 返回第k个元素
Node* kth(int k) {
Node* o = root;
while(o != null) {
int d = o->cmp(k);
if(d == -) return o;
if(d == ) k -= o->ch[]->s + ;
o = o->ch[d];
}
return null;
}
// 读取第k个元素
type operator[](int k) {
return kth(k)->v;
}
// 返回元素个数
int size() {
return root->s;
}
// 初始化、清空序列
void init() {
for(int i = ; i < MAXS; i++) stk[i] = &mem[i];
top = MAXS - ;
null = newNode();
null->s = ;
root = null;
}
// 中序遍历输出整个序列
void print(Node* o) {
if(o == null) return;
o->pushdown();
print(o->ch[]);
printf("%d ", o->v);
print(o->ch[]);
}
private:
static const int MAXS = 1e6 + ; // 最大结点数
Node* null;
int top;
Node* stk[MAXS];
Node mem[MAXS];
void rotate(Node* &o, int d) {
Node* k = o->ch[d^];
o->ch[d^] = k->ch[d];
k->ch[d] = o;
o->maintain();
k->maintain();
o = k;
}
void splay(Node* &o, int k) {
o->pushdown();
int d = o->cmp(k);
if(d == -) return;
if(d == ) k -= o->ch[]->s + ;
Node* p = o->ch[d];
p->pushdown();
int d2 = p->cmp(k);
int k2 = (d2 == ? k : k - p->ch[]->s - );
if(d2 != -) {
splay(p->ch[d2], k2);
if(d == d2) rotate(o, d^);
else rotate(o->ch[d], d);
}
rotate(o, d^);
}
Node* newNode() {
return stk[top--];
}
void delNode(Node* o) {
stk[++top] = o;
}
}; SplaySequence<int> ss; int main() {
int n, m;
scanf("%d%d", &n, &m);
ss.init();
for(int i = ; i <= n; i++) ss.insert(ss.size(), i);
for(int p, s, i = ; i < m; i++) {
scanf("%d%d", &p, &s);
SplaySequence<int>::Node *left, *mid, *right, *o;
ss.split(ss.root, p-, left, o);
ss.split(o, s, mid, right);
ss.root = ss.merge(ss.merge(mid, left), right);
}
ss.print(ss.root);
return ;
}
rope版
#include <cstdio>
#include <ext/rope>
using namespace __gnu_cxx; rope<int> r; int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) r.push_back(i);
for(int p, s, i = ; i < m; i++) {
scanf("%d%d", &p, &s);
p--;
r = r.substr(p, s) + r.substr(, p) + r.substr(p+s, n-p-s);
}
for(int i = ; i < n; i++) printf("%d ", r[i]);
return ;
} /*
r.push_back(x); // 在末尾添加x
r.insert(pos, x); // 在pos插入x
r.erase(pos, x); // 从pos开始删除x个
r.copy(pos, len, x); // 从pos开始到pos+len为止用x代替
r.replace(pos, x); // 从pos开始换成x
r.substr(pos, x); // 提取pos开始x个
r.at(x) / [x]; // 访问第x个元素
时间复杂度为n*(n^0.5)
*/