题解：P4940 Portal2

· · 题解

传送门 | AC 记录

Description

用 Q\le 10^6 次操作维护 2 个栈，最后输出栈内元素。

Solution

题解区有手搓双向链表的大佬，但貌似用多个 std::list 辅助实现更简单，因为它除了【链接两个链表】以外的操作都帮我们写好了。

于是我们对常规操作进行如下改动：

链接

由于没有相关接口，无法直接访问链头、链尾地址，所以考虑使用插入路牌，即在需要链接的两端插入对方端的信息作为路牌，以便访问到此时直接跳转。

在本题，要用到此操作的只有 MOVE x y。可以发现，其相当于把 y 反转后压入 x 顶，原因可看楼下。因此，只需将 x,y 的顶部链接，然后将 y 的底部作为新的 x 的顶部并为 y 申请新的位置。

涉及到头尾的交换，所以需要记录它们的绝对位置（所在链表的下标） 和 方向（位于链表的哪一端）。用 t_x,b_x 分别表示 x 号栈顶部、底部的绝对位置，初始为 x+1。用 et_x,eb_x\in\{0,1\} 分别表示 x 号栈顶部、底部的方向，初始为 et_x=0,eb_x=1。

而对路牌的构造，需要一个包含 t,et 并且和普通值区分的数字。有以下信息：

  1. 普通值非负。

所以路牌选择 -(t_x\times 10+et_x)。

MOVE 1 0 的过程演示：

部分代码：

// 1. 插入路牌
ll tmp1=-(t[x]*10+et[x]);
ll tmp2=-(t[y]*10+et[y]);
PUSH(x,tmp2);
PUSH(y,tmp1);
// 2. 修改接口数据 
t[x]=b[y],et[x]=eb[y];
// 3. 将 y 迁移至新位置 
t[y]=b[y]=++l;
et[y]=0,eb[y]=1;

插入 / 弹出 / 取值

判断头或尾方向，调用对应函数即可。可用宏实现。

部分代码：

#define PUSH(X,Y) \
({ if(et[(X)]==0) s[t[(X)]].push_front((Y)); \
   else           s[t[(X)]].push_back((Y)); })

#define POP(X) \
({ if(et[(X)]==0) s[t[(X)]].pop_front(); \
   else           s[t[(X)]].pop_back(); })

#define TOP(X)    (et[(X)]==0 ? s[t[(X)]].front() : s[t[(X)]].back())
#define BOTTOM(X) (et[(X)]==0 ? s[t[(X)]].back()  : s[t[(X)]].front())

遍历

反复弹出头部元素，如果是路牌就跳转，并把对面的也删除（路牌总是成对出现）。

部分代码：

while(!s[t[x]].empty()) {
    ll tmp=TOP(x); POP(x);
    if(tmp<0) {
        et[x]=(-tmp)%10,t[x]=(-tmp)/10;
        POP(x);
    }// 发现路牌，跳转 
    else {/* 在这做一些事 */}
}

基本准备好后，剩下只需按要求模拟即可。

PUSH

直接调用 PUSH 即可。

POP

遍历直到成功取出非路牌。

ADD / SUB

遍历两栈直到成功取出非路牌，相加 / 减再 PUSH。若其中一个未成功取出就抛出错误，并把取出来没用上的再压回去（忽略该指令，要还原）。

DEL

考虑到每次都将栈内元素清空，总时间复杂度为 \mathcal{O}(n)，直接遍历删除即可。

MOVE

上面【链接】的实现里讲过，不再多说。

SWAP

交换接口数据即可，即分别交换 t,b,et,eb。

END

遍历输出，记录是否成功输出。

Code

#include<iostream>
#include<list>
using namespace std;
using ll=long long;
#define SU cout<<"SUCCESS\n"
#define UN cout<<"UNSUCCESS\n"
// 定义宏时勤加括号 { } ( )
#define PUSH(X,Y) \
({ if(et[(X)]==0) s[t[(X)]].push_front((Y)); \
   else           s[t[(X)]].push_back((Y)); })

#define POP(X) \
({ if(et[(X)]==0) s[t[(X)]].pop_front(); \
   else           s[t[(X)]].pop_back(); })

#define TOP(X)    (et[(X)]==0 ? s[t[(X)]].front() : s[t[(X)]].back())
#define BOTTOM(X) (et[(X)]==0 ? s[t[(X)]].back()  : s[t[(X)]].front())
list<ll>s[(int)1e6+2];
// s[0] 不使用，因为 -0=0 不能作为路牌
string op;
ll x,y,t[2]={1,2},et[2]={0,0},b[2]={1,2},eb[2]={1,1},l=2;
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(cin>>op) {
        if(op=="END") break;
        else if(op=="PUSH") {
            cin>>x>>y;SU;
            PUSH(x,y);
        }
        else if(op=="POP") {
            cin>>x;
            bool SU_pop=0;// 记录是否成功弹出 
            while(!s[t[x]].empty()) {
                ll tmp=TOP(x); POP(x);
                if(tmp<0) {
                    et[x]=(-tmp)%10,t[x]=(-tmp)/10;
                    POP(x);
                }
                else { SU_pop=1;SU;break;}
            }
            if(!SU_pop) UN;
        }
        else if(op=="ADD"||op=="SUB") {
            cin>>x;
            ll tmp1=-1,tmp2=-1;
        // 遍历 2 个栈并找到顶部元素，找不到就报错 
        // 与 POP 中的基本相同 
            while(!s[t[0]].empty()) {
                ll tmp=TOP(0); POP(0);
                if(tmp<0) {
                    et[0]=(-tmp)%10,t[0]=(-tmp)/10;
                    POP(0);
                }
                else { tmp1=tmp;break;}
            }
            if(tmp1==-1) { UN;continue;}
            while(!s[t[1]].empty()) {
                ll tmp=TOP(1); POP(1);
                if(tmp<0) {
                    et[1]=(-tmp)%10,t[1]=(-tmp)/10;
                    POP(1);
                }
                else { tmp2=tmp;break;}
            }
            if(tmp2==-1) { PUSH(0,tmp1);UN;continue;}// 注意要把没用上的 tmp1 再 push 回去 
            if(op=="ADD") PUSH(x,tmp1+tmp2);
            else PUSH(x,abs(tmp1-tmp2));
            SU;
        }
        else if(op=="DEL") {
            cin>>x;SU;
            while(!s[t[x]].empty()) {
                ll tmp=BOTTOM(x);
                s[t[x]].clear();
                if(tmp<0) {
                    et[x]=(-tmp)%10,t[x]=-tmp/10;
                    POP(x);
                }
            }
        }
        else if(op=="MOVE") {
            cin>>x>>y;SU;
            ll tmp1=-(t[x]*10+et[x]);
            ll tmp2=-(t[y]*10+et[y]);
            PUSH(x,tmp2);
            PUSH(y,tmp1);
            t[x]=b[y],et[x]=eb[y];
            t[y]=b[y]=++l;
            et[y]=0,eb[y]=1;
        }
        else if(op=="SWAP") {
            SU;
            swap(t[0],t[1]);
            swap(et[0],et[1]);
            swap(b[0],b[1]);
            swap(eb[0],eb[1]);
        }
    }
    SU;
// 以下部分与 POP / ADD 中的基本相同 
    bool SU_out=0;
    while(!s[t[0]].empty()) {
        ll tmp=TOP(0); POP(0);
        if(tmp<0) {
            et[0]=(-tmp)%10,t[0]=(-tmp)/10;
            POP(0);
        }
        else cout<<tmp<<' ',SU_out=1;
    }
    if(!SU_out) cout<<"NONE";
    cout<<'\n';
    SU_out=0;
    while(!s[t[1]].empty()) {
        ll tmp=TOP(1); POP(1);
        if(tmp<0) {
            et[1]=(-tmp)%10,t[1]=(-tmp)/10;
            POP(1);
        }
        else cout<<tmp<<' ',SU_out=1;
    }
    if(!SU_out) cout<<"NONE";
    return 0;
}