Description
最近小M买了一个移动硬盘来储存自己电脑里不常用的文件。但是他把这些文件一股脑丢进移动硬盘后，觉得这些文件似乎没有被很好地归类，这样以后找起来岂不是会非常麻烦？
小M最终决定要把这些文件好好归类，把同一类地移动到一起。所以现在小M有了这几种操作：
1 u 表示把编号为u的文件放到最上面
2 u 表示把编号为u的文件放到最下面
3 u v 表示把编号为u的文件放到编号为v的文件的后面
已知在最开始的时候，1号文件到n号文件从上往下排布
现在小M已经给出了他所进行的所有操作，你能告诉他操作之后的序列是会变成什么样子吗？
Input
第一行为一个数字T（T<=10）表示数据组数
第二行为两个数字n、m（1<=n,m<=300000）表示序列长度和小M的操作次数
接下来m行每行两个或三个数字，具体含义见题面
保证数据合法
Output
输出一行表示小M操作结束后的序列
Sample Input
1
10 5
1 5
2 3
2 6
3 4 8
3 1 3
Sample Output
5 2 7 8 4 9 10 3 1 6
Hint
这道题之前见过好几次，没有一次写出来过，前几天认真研究了一下，终于写出来了。
思路：对每个位置，用l 和r两个数组记录该位置前面和后面的数的编号，每次变动的时候更新一下就好了。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAXN 300010
typedef long long ll;
int m, n;
int l[MAXN], r[MAXN];
void init()
{
r[0] = 1;
l[n + 1] = n;
for (int i = 1; i <= n; i++)
{
l[i] = i - 1;
r[i] = i + 1;
}
}
void con(int x, int y)
{
r[x] = y;
l[y] = x;
}
int main()
{
int T,x,u,v;
while (cin >> T)
{
while (T--)
{
cin >> n >> m;
init();
for (int i = 0; i < m; i++)
{
cin >> x;
if (x == 1)
{
cin >> u;
if (r[0] == u)
continue;
int l_u = l[u],r_u=r[u],r0=r[0];
con(l_u, r_u);
con(u, r0);
con(0, u);
}
else if (x == 2)
{
cin >> u;
if (l[n+1] == u)
continue;
int l_u = l[u], r_u = r[u], l_n = l[n+1];
con(l_u, r_u);
con(l_n, u);
con(u, n+1);
}
else
{
cin >> u >> v;
if (r[v] == u)
continue;
int l_u = l[u], r_u = r[u], r_v = r[v];
con(l_u, r_u);
con(u, r_v);
con(v, u);
}
}
int temp = r[0];
cout << temp;
while (r[temp] != (n + 1))
{
cout << " " << r[temp];
temp = r[temp];
}
cout << endl;
}
}
return 0;
}
/**********************************************************************
Problem: 1982
User: leo6033
Language: C++
Result: AC
Time:984 ms
Memory:4368 kb
**********************************************************************/
这题还能用链表来写，可以自己思考思考