Problem

Editor

Editor-Problem.png

Sample Input

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

Sample Output

2
3

Hint

The following diagram shows the status of sequence after each instruction:

Editor-Hint.png

思路

手寫一個(gè)可遍歷的棧，然后模擬操作~~

代碼

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1e6 + 5;
int a[M];
class Stack {
private:
    int size;
    int a[M];
public:
    Stack() :size(0) { memset(a, 0, sizeof(a)); }
    void init() { size = 0; memset(a, 0, sizeof(a)); }
    bool empty() { return size == 0; }
    void push(int x) { a[size++] = x; }
    void pop() { --size; }
    int top() { return a[size - 1]; }
    int get(int k) { return a[k - 1]; }
};
Stack L, R;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int Q;
    char c;
    while (cin >> Q) {
        memset(a, 0, sizeof(a));
        L.init(); R.init();
        int step = 0, sum = 0;
        while (Q--) {
            cin >> c;
            if (c == 'I') {
                cin >> a[step];
                sum += a[step++];
                if (L.empty())L.push(sum);
                else L.push(max(sum, L.top()));
            }
            else if (c == 'D' && !L.empty()) {
                sum -= a[--step];
                L.pop();
            }
            else if (c == 'L' && !L.empty()) {
                R.push(a[--step]);
                sum -= a[step];
                L.pop();
            }
            else if (c == 'R' && !R.empty()) {
                a[step] = R.top();
                R.pop();
                sum += a[step++];
                if (L.empty())L.push(sum);
                else L.push(max(sum, L.top()));
            }
            else if (c == 'Q') {
                int k;
                cin >> k;
                cout << L.get(k) << endl;
            }
        }
    }
    return 0;
}