链接：https://www.nowcoder.com/acm/contest/141/C
来源：牛客网

Shuffle Cards

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

Eddy likes to play cards game since there are always lots of randomness in the game. For most of the cards game, the very first step in the game is shuffling the cards. And, mostly the randomness in the game is from this step. However, Eddy doubts that if the shuffling is not done well, the order of the cards is predictable!
To prove that, Eddy wants to shuffle cards and tries to predict the final order of the cards. Actually, Eddy knows only one way to shuffle cards that is taking some middle consecutive cards and put them on the top of rest. When shuffling cards, Eddy just keeps repeating this procedure. After several rounds, Eddy has lost the track of the order of cards and believes that the assumption he made is wrong. As Eddy's friend, you are watching him doing such foolish thing and easily memorizes all the moves he done. Now, you are going to tell Eddy the final order of cards as a magic to surprise him.
Eddy has showed you at first that the cards are number from 1 to N from top to bottom.
For example, there are 5 cards and Eddy has done 1 shuffling. He takes out 2-nd card from top to 4-th card from top(indexed from 1) and put them on the top of rest cards. Then, the final order of cards from top will be [2,3,4,1,5].

输入描述:

The first line contains two space-separated integer N, M indicating the number of cards and the number of shuffling Eddy has done.
Each of following M lines contains two space-separated integer pi, si indicating that Eddy takes pi-th card from top to (pi+si-1)-th card from top(indexed from 1) and put them on the top of rest cards.


1 ≤ N, M ≤ 105
1 ≤ pi ≤ N
1 ≤ si ≤ N-pi+1

输出描述:

Output one line contains N space-separated integers indicating the final order of the cards from top to bottom.

示例1

输入

复制

5 1
2 3

输出

复制

2 3 4 1 5

示例2

输入

复制

5 2
2 3
2 3

输出

复制

3 4 1 2 5

示例3

输入

复制

5 3
2 3
1 4
2 4

输出

复制

3 4 1 5 2

题意：给你N张牌，初始顺序为1....n;有M次洗牌操作；

（qi,si) 表示从【1，n】中 拿第qi张牌+si张牌 放到最上面（类似洗牌）

问  到最后牌面的顺序是？

一开始我用string的函数 

     s.substr(l,c);//从l位置往后截取c个字符 （索取号从0开始
      s.erase(l,c);/从l位置往后删除c个字符

#include<bits/stdc++.h> using namespace std; const int M=100005; int main() { int l,c,n,m,i; while(cin>>n>>m)
  { string a,s,ss; char ch[100005]; for(int i=0; i<n; i++) ch[i]=i+'1';
    ch[n]='\0';
    a=ch; while(m--)
    { cin>>l>>c; if(l==1) continue;//不变 s=a.substr(l-1,c); //cout<<s<<endl;//从l-1位置往后截取c个字符 a.erase(l-1,c);//cout<<a<<"\n";//从l-1位置往后删除c个字符 a=s+a;//合并 //cout<<a<<"\n"; } for(i=0; i<n-1; i++)
    { printf("%c ",a[i]);
    } printf("%c\n",a[i]);

  }
}

但是不知为何会越界。。。（希望那位大佬知道的可以告诉我•ᴗ•）

后来学了 Rope函数

类似指针链表的操作，时间复杂度会在n*(n^0.5)，可以在很短的时间内实现快速的插入、删除和查找字符串

在g++头文件中，<ext/rope>中有成型的块状链表，在using namespace __gnu_cxx;空间中，类似string函数的操作其操作十分方便。

基本操作：

rope T;

T.push_back(x);//在末尾添加x

T.insert(pos,x);//在pos插入x

T.erase(pos,x);//从pos开始删除x个

T.copy(pos,len,x);//从pos开始到pos+len为止用x代替

T.replace(pos,x);//从pos开始换成x

T.substr(pos,x);//提取pos开始x个

T.at(x)/[x];//访问第x个元素

printf("%d\n",T[i])   cout<<T<<endl; 输出T[i] 输出T；

AC代码：

#include <bits/stdc++.h> #include <ext/rope>//函数头文件 using namespace __gnu_cxx; using namespace std; const int maxn=1e5+10;

rope<int> T; int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) T.push_back(i); while (m--)
  { int p,s; scanf("%d%d",&p,&s);
    p--;
    T=T.substr(p,s) + T.substr(0,p) + T.substr(p+s,n-p-s); //洗牌后的顺序 中间 +前部 +后面 } for (int i=0; i<n; i++) printf("%d ",T[i]); return 0;
}