有 n 个人排队,1 号排在 2 号前面,2 号排在 3 号前面,…,以此类推 n−1 号排在 n 号前面。在这个过程中,偶尔老师会把某个人叫走,叫走之后这个人就离开了队伍,假设本来 a排在 b 前面,b 排在 c前面b 被叫走后 a 就排在了 c 前面。老师偶尔也会感到疑问,她想知道此时排在 a 号前面的同学是几号呢?
已知老师一共会有 k 次操作,每次会执行下面的一种:
- 把 xx 叫走。
- 求排在 xx 前面的是谁。
#include<iostream>
using namespace std;
int arr[1000005];
struct Node{
long long l,r;//定义结构体
}lst[1000005];
int main()
{long long n,m,a,b;cin>>n>>m;for(int i=1;i<=n;i++){lst[i].l=i-1;lst[i].r=i+1;}while(m--){cin>>a>>b;if(a==1) {lst[lst[b].l].r=lst[b].r;lst[lst[b].r].l=lst[b].l;;}elsecout<<lst[b].l<<endl; }return 0;
}