Skip to content

11622: 【原1622】Sakuya

题目

题目描述

author: Chika 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1622 ## Description

你大概被送至了过去的十六夜月下。

于是你见到了一道好像似乎见过的题目。(啊呀好像并不存在能使时间倒退的设定呢

题目大意是让你维护一个栈,里面每一个数都是0或者1。弹栈顶和入栈大概都是一些常见的设定。

这题有趣之处在于多了一个栈翻转,你可以考虑就是将整个栈倒立过来。

另外的维护的东西是从栈顶到栈底的数的与非的值,举个栗子:

假设这个栈从栈顶到栈底是a1, a2, a3, a4,那么你要得到的就是((a1 nand a2) nand a3) nand a4.

与非的设定大概是先与运算再取非运算,也即x nand y = not (x and y)。

你似乎永远都解不开这道题目,因为你的时间已经停止了呢。

Input Format

第一行是一个数n,表示操作个数

接下来n行,每一行代表一种可能的事件。

  • PUSH x: 将x压入栈
  • POP: 将栈顶弹出
  • REVERSE: 将整个栈翻转
  • QUERY: 询问当前栈的答案,如果栈空了,你应当输出"Invalid."

Output Format

对于每一个询问类事件,输出对应的答案或者是"Invalid."。

Sample Input

8
PUSH 1
QUERY
PUSH 0
REVERSE
QUERY
POP
POP
QUERY

Sample Output

1
1
Invalid.

Limits

  • 对于100%的数据,n <= 200000

zqy2018's solution

/*
    Hint: use a deque to replace the stack and find the relation between the result 
        and the length of consecutive 1's at the front/back of the deque
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, fa[200005], len[200005] = {0};
int val[200005] = {0};
deque<int> dq;
char opt[10];
void init(){
    n = read();
}
int Find(int x){
    return (fa[x] == x ? x: (fa[x] = Find(fa[x])));
}
void solve(){
    bool rt = true;
    for (int i = 1; i <= n; ++i){
        scanf("%s", opt);
        if (opt[0] == 'P'){
            if (opt[1] == 'U'){
                int x = read();
                fa[i] = i, val[i] = x;
                if (rt){
                    if (x == 0) len[i] = 0;
                    else {
                        if (!dq.empty() && val[dq.back()])
                            fa[i] = Find(dq.back()), ++len[fa[i]];
                        else 
                            len[i] = 1;
                    }
                    dq.push_back(i);
                }else {
                    if (x == 0) len[i] = 0;
                    else {
                        if (!dq.empty() && val[dq.front()])
                            fa[i] = Find(dq.front()), ++len[fa[i]];
                        else 
                            len[i] = 1;
                    }
                    dq.push_front(i);
                }
            }else{
                if (dq.empty()) continue;
                if (rt) {
                    if (val[dq.back()])
                        --len[Find(dq.back())];
                    dq.pop_back();
                }else {
                    if (val[dq.front()])
                        --len[Find(dq.front())];
                    dq.pop_front();
                }
            }
        }
        if (opt[0] == 'R'){
            rt = !rt;
        }
        if (opt[0] == 'Q'){
            if (dq.empty()){
                printf("Invalid.\n");
            }else {
                if (dq.size() == 1){
                    printf("%d\n", val[dq.front()]);
                }else if (dq.size() == 2){
                    printf("%d\n", (val[dq.front()] & val[dq.back()]) ^ 1);
                }else {
                    if (!rt) {
                        int ll = len[Find(dq.back())];
                        if (ll >= dq.size() - 1)
                            printf("%d\n", ll & 1);
                        else printf("%d\n", (ll + 1) & 1);
                    }else {
                        int ll = len[Find(dq.front())];
                        if (ll >= dq.size() - 1)
                            printf("%d\n", ll & 1);
                        else printf("%d\n", (ll + 1) & 1);
                    }
                }
            }
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}