FZU 2091 播放器

Description

shadow喜歡聽音樂，于是v11自己寫了個播放器送給了shadow，這個播放器有一個播放清單，一個“下一首”按鈕，一個“上一首”按鈕，還有一個播放記錄。

一開始播放器會播放播放清單中的第一首歌，當按下“下一首”按鈕時，它會播放目前歌曲在播放清單中的下一首歌，若目前歌曲就是播放清單中的最後一首歌時，它仍會播放播放清單中的最後一首歌；當按下“上一首”按鈕時，它會清除播放記錄中的最後一首歌，并播放清除後播放記錄中的最後一首歌，若清除後播放記錄為空，則播放播放清單中的第一首歌；當按下播放清單中的某一首歌曲，它會播放該首歌曲。

任何時候，當播放器播放一首歌時，如果該歌曲與播放記錄中的最後一首不同或者播放記錄為空，便将該歌曲添加到播放記錄中成為最後一首。

現在shadow對播放器進行了一系列操作，那麼你能告訴我shadow進行每一個操作後，播放器在播放哪首歌嗎？

Input

輸入資料第一行包含一個整數T，表示測試資料的組數。對于每組測試資料：

第一行包含兩個整數n( 0 < n <= 500 )、m( 0 < m <= 10000)，分别表示播放清單中有n首歌曲，shadow進行了m項操作，播放清單中歌的編号依次為1,2,3……n 。

接下來m行，每行為以下三種形式之一：

PRE 表示按下了“上一首”按鈕。

PLAY x 其中x為一個整數( 0 < x <= n )，表示按下了播放清單中的第x首歌。

NEXT 表示按下了“下一首”按鈕。

Output

對于每組資料：輸出m行，每行一個整數，表示執行了一項操作後播放器正在播放的歌曲。

Sample Input

1

5 10

PRE

NEXT

PLAY 5

NEXT

PLAY 5

PLAY 3

NEXT

PRE

PRE

PRE

Sample Output

1

2

5

5

5

3

4

3

5

2

簡單的棧操作，注意一開始是第一首歌

#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=5e3+10;
stack<int> p;
int T,n,m,x;
char s[maxn];

int main()
{
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d%d",&n,&m);
    while (!p.empty()) p.pop();
    p.push(1);
    while (m--)
    {
      scanf("%s",s);
      if (s[1]=='R')
      {
        p.pop();
        if (p.empty()) p.push(1);
      }
      if (s[1]=='L') 
      {
        scanf("%d",&x);
        if (x!=p.top()) p.push(x);
      }
      if (s[1]=='E')
      {
        int x=p.top();
        if (x<n) p.push(x+1);
      }
      printf("%d\n",p.top());
    }
  }
  return 0;
}