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 第一次用链表做题,用一个数组保存每个数字所在的地址就可以实现O（1）查找了，坑了我很久，我开始建了一个循环双链表,结果死活WA(好像问题是出在第二步移动操作了),然后我将尾指针弃之不用,每次都是插在尾指针前面,然后就AC了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include <string.h>
#include <math.h>
using namespace std;
const int N =;
typedef long long LL;
typedef struct LNode{
int data;
struct LNode *next,*pre;
}*LinkList,LNode; LinkList id[N];
LinkList L,tail;
void create(int n,LinkList &L,LinkList &tail){
LinkList p,r;
r = new LNode;
tail = new LNode;
L->next = L->pre = L;
L = r;
int i= ;
while(i<=n){
p = new LNode;
p->data = i;
id[i] = p;
i++;
r->next = p;
p->pre = r;
r = p;
}
r->next = tail;
tail->pre = r;
} void HeadInsert(LinkList &L,LinkList &p){
p->next = L->next;
L->next = p;
p->pre = L;
p->next->pre = p;
} void TailInsert(LinkList &tail,LinkList &p){
tail->pre->next = p;
p->pre = tail->pre;
p->next = tail;
tail->pre = p;
} void InsertUV(LinkList &p,LinkList &q){
q->next->pre = p;
p->pre = q;
p->next = q->next;
q->next = p;
}
void Travel(LinkList L){
LNode *p = L->next;
while(p!=tail){
printf("%d ",p->data);
p = p->next;
}
} int main()
{
int tcase;
scanf("%d",&tcase);
int n,m;
while(tcase--)
{ L = new LNode;
scanf("%d %d",&n,&m);
create(n,L,tail);
int op,u,v;
while(m--){
scanf("%d",&op);
if(op==){
scanf("%d",&u);
LinkList p = id[u];
if(L->next ==p) continue;
p->pre->next = p->next;
p->next->pre = p->pre;
HeadInsert(L,p);
}
if(op==){
scanf("%d",&u);
LinkList p = id[u];
if(p==tail) continue;
p->pre->next = p->next;
p->next->pre = p->pre;
TailInsert(tail,p);
//Travel(L);
}
if(op==){
scanf("%d %d",&u,&v);
LinkList p = id[u],q = id[v];
if(p==q) continue;
p->pre->next = p->next;
p->next->pre = p->pre;
InsertUV(p,q);
}
}
Travel(L);
LinkList p=L,q;
while(p!=tail){
q = p;
p=p->next;
delete q;
}
delete tail;
printf("\n");
} return ;
}