連結：https://www.nowcoder.com/acm/contest/141/C
來源：牛客網
題意：
一副有N(N<=1e5)張卡片的牌，初始從頂部到底部的牌号分别是1到N，給出M(M<=1e5)次洗牌操作，每次洗牌操作給出兩個整數p和s，表示從頂部往下數第p個位置開始的s張牌從牌堆中取出，放到頂部。
樣例輸入：
5 1
2 3
樣例輸出：
2 3 4 1 5
樣例輸入：
5 2
2 3
2 3
樣例輸出：
3 4 1 2 5
題目分析：
好吧，賽後師兄們說就是一個平衡樹的模闆題，但是強大的chen_jr_他們隊能用一個強大的stl代替實作，雖然時間多了點但是這題并不卡這點時間，這個STL就是rope啦，先學一下rope的基本用法，但是treap還是需要學的！！
rope模闆：
#include <ext/rope>
using namespace __gnu_cxx;
//以上兩個東西是使用rope需要用的
//1.聲明
rope<int>t;
//2.初始化
t.clear();
//3.操作
t.push_back(x);//在末尾添加x(元素)
t.insert(pos, x);//在pos位置(pos=0...t.size()-1)插入x(元素/rope)
t.copy(pos, x, to);//把rope從pos開始的x個元素，覆寫到指針node* to中
t.replace(pos, x, y);//從pos開始的x個換成y(元素/rope)
t.replace(pos, x);//第pos個換成x(元素/rope)
t.erase(pos, x);//從pos開始删除x個
t.substr(pos, x);//提取pos開始x個
t.at(pos) / t[pos];//通路pos位置元素
AC代碼——rope：
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
rope<int>s,tmp;
int n,m,l,r;
int main() {
while (~scanf("%d %d",&n,&m)){
s.clear();
for(int i=1;i<=n;i++)s.push_back(i);
for(int i=1;i<=m;i++){
scanf("%d %d",&l,&r);
tmp=s.substr(l-1,r);
s.erase(l-1,r);
s=tmp+s;
}
for(int i=0;i<n;i++)printf("%d%c",s[i],i==n-1?'\n':' ');
}
return 0;
}
PS：各種樹，太強辣！！一定要學
AC代碼——treap：
#include <bits/stdc++.h>
using namespace std;
const int T = 1e6 + 6; // 節點數量, 同時也是所維護的序列的長度
int lch[T], rch[T], siz[T], fix[T], n; int key[T];
// lch[t]: left child, t 的左孩子
// rch[t]: right child, t 的右孩子
// siz: t 子樹的規模
// fix: t 節點的随機權值，越大的位置越高
// key: t 節點的關鍵字值
int tot, root;
// tot: 已使用節點數量，包括空節點 (0 号元素) 在内
// root: 如等于 0，表示空樹，否則表示一棵 treap 的根節點
inline void reset() { root = 0; tot = 1; }
// 建立一個節點，生成随機權值，保證高度為期望 O(log T), 并令它的關鍵字為 x, 傳回節點的編号
inline int newnode(int x){
int t = tot; ++tot; /* assert(tot<=T); */
lch[t] = rch[t] = 0, siz[t] = 1; // siz 域是要把自己也算進去的
fix[t] = rand() << 15 | rand(); // 普通的 rand() 隻能産生 (1<<15) 以内的整數，需要做兩次之後拼接起來
key[t] = x;
return t;
}
// 如果你需要懶标記，可以把維護過程補在這裡，比如說區間翻轉，區間求最值等操作（本程式沒有展現，故為空白，連形參都省略）
inline void pushdown(int){}
// 如無上述特殊詢問，update 負責維護 siz 域
inline void update(int t){
siz[t] = siz[lch[t]] + 1 + siz[rch[t]];
}
// 把 t 以第 k 名為界分割成 l 和 r 兩半，k 按人類的思維從 1 開始編号，其中第 k 名将落入 r 中。
void split(int t, int k, int &l, int &r){
if (!t){ l = r = 0; /*assert(k==1);*/ return; }
pushdown(t);
int tk = siz[lch[t]] + 1;
if (k <= tk){
split(lch[t], k, l, lch[t]); r = t;
}
else{
split(rch[t], k - tk, rch[t], r); l = t;
}
update(t);
}
// 将 l 和 r 合并成 t，如合并後以中序周遊檢視 t 的内容，則有 l 的内容排在 r 的前面。
void join(int &t, int l, int r){
if (!l){ t = r; return; }
if (!r){ t = l; return; }
if (fix[l]>fix[r]){
pushdown(t = l); join(rch[l], rch[l], r);
}
else{
pushdown(t = r); join(lch[r], l, lch[r]);
}
update(t);
}
// 在 t 中尋找第 k 名元素，并傳回其編号（注意是編号，不是其關鍵字）（這在設計上和 STL set 的 find 函數如出一轍）
int find(int t, int k){
pushdown(t);
int tk = siz[lch[t]] + 1;
if (k == tk)return t;
if (k<tk) return find(lch[t], k);
return find(rch[t], k - tk);
}
// 查詢 t 中第一個大于等于 x 的關鍵字（這在設計上和 STL set 的 lower_bound 函數也是如出一轍）
int order(int t, int x){
if (!t)return 1;
pushdown(t);
if (x <= key[t])return order(lch[t], x);
return siz[lch[t]] + 1 + order(rch[t], x);
}
inline void insert(int x){
int l, r, k = order(root, x), t = newnode(x);
split(root, k, l, r);
join(r, t, r);
join(root, l, r);
}
void work(int p, int len){
int l, r, m;
split(root, p, l, r);
split(r, len + 1, m, r);
join(root, l, r);
join(root, m, root);
}
vector<int> ans;
void display(int u){
if (u == 0)return;
display(lch[u]);
ans.push_back(u);
display(rch[u]);
}
int main(){
int n, m;
while (scanf("%d %d", &n, &m) != -1){//n張牌1到n，m次洗牌
reset();//初始化，空樹，隻有空節點root
for (int i = 1; i <= n; i++){
insert(i); //插入值
}
for (int i = 1; i <= m; i++){
int p, s, L, MID, R;
scanf("%d %d", &p, &s);
split(root, p, L, MID);//把root樹拆成L(1到p-1)和MID(p到n)
split(MID, s + 1, MID, R);//把MID樹拆成MID(p到p+s)和R(p+s+1到n)
join(L, MID, L);//将MID和L合并成L，MID作為左邊，L作為右邊
join(root, L, R);//将L和R合并成root，MID作為左邊，L作為右邊
}
ans.clear();
display(root);//周遊答案
for (int i = 0; i<ans.size(); i++){
printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
}
}
}
![伸展樹(splay)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)