自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:05:29，当前版本为作者最后更新于2019-03-17 13:49:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$Updata$发现打错了几个符号和字……

上一篇唯一的题解涉嫌抄袭被$Delete$了（考古
那我来补一篇

先扯一句，题面说什么无效操作，事实上没有（弄的我多打了100行……

从题面透露出的信息我们可以感受到这题是个大型模拟

看到目前的提交大多数是栈和链表
然而本蒟蒻并不会，所以就打了一个双端队列（模拟栈）+启发式合并

除了$MOVE$操作，其他操作还是比较简单吧……按照题意打就可以了

对于$MOVE$操作我们进行启发式合并，因为最多有$10^6$次操作，如果按照题意暴力合并复杂度能够达到$O(N^2)$，而启发式合并能够保证复杂度为$O(N log_2 N)$

我们开两个双端队列模拟栈，最初队首为栈底，队尾为栈顶，前面四个操作直接在队尾执行，每次复杂度$O(1)$

对于第5个操作$DEL$，直接暴力讲队列清空，每次复杂度$O(n)$，均摊复杂度$O(1)$

对于第7个操作$SWAP$，我们记录$f_0$和$f_1$，表示输入的$x$号栈对应的是第$f_x$号队列，操作时直接讲$f_0$和$f_1$ $SWAP$即可，注意，$f_0 f_1$一定要分别置初值${0,1}$，每次复杂度$O(1)$

对于毒瘤的第6个操作$MOVE$，我们考虑两种情况（注意，题目要求将$Y$栈移动到$X$栈）：

• 当$Y$栈小于$X$栈时，直接暴力将$Y$栈里的元素移到$X$栈里

• 当$Y$栈大于$X$栈
  我们借助$Tag_0\text{和}Tag_1$表示这个队列是否反转，即队头变队尾，队尾变队头，初始化都为零，表示没有反转
  我们将$X$栈里的元素按照出栈顺序一一移动到$Y$栈
  然后再将$Tag_Y\ XOR\ \ 1$，因为两次反转则等于没有反转
  最后$SWAP(f_x,f_y)$
  为什么这样是对的，因为将$Y$栈移动到$X$栈正好是将$X$栈移动到$Y$栈的反转序列，自己画个图就知道了

每次复杂度$O(n)$，均摊复杂度$O(log_2N)$

$Code:$ $O(N log_2 N)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
deque<ll>q[2];
int f[2]={0,1};
int tag[2]={0,0};
int main()
{
    char k[10];int x,y;ll X,Y;
    while(true){
        scanf("%s",k);
        if(k[0]=='P'&&k[1]=='O'){
            scanf("%d",&x);
            if(!q[f[x]].size()){
                puts("UNSUCCESS");
            }
            else{
                puts("SUCCESS");
                if(tag[f[x]]){
                    q[f[x]].pop_front();
                }
                else q[f[x]].pop_back();
            }
        }
        else if(k[0]=='P'&&k[1]=='U'){
            scanf("%d%lld",&x,&Y);
            puts("SUCCESS");
            if(tag[f[x]]){
                q[f[x]].push_front(Y);
            }
            else q[f[x]].push_back(Y);
        }
        else if(k[0]=='A'&&k[1]=='D'){
            scanf("%d",&x);
            if(!q[0].size()||!q[1].size()){
                puts("UNSUCCESS");
            }
            else{
                puts("SUCCESS");
                ll a,b;
                if(tag[0])a=q[0].front(),q[0].pop_front();
                else a=q[0].back(),q[0].pop_back();
                if(tag[1])b=q[1].front(),q[1].pop_front();
                else b=q[1].back(),q[1].pop_back();
                if(tag[f[x]]){
                    q[f[x]].push_front(a+b);
                }
                else{
                    q[f[x]].push_back(a+b);
                }
            }
        }
        else if(k[0]=='S'&&k[1]=='U'){
            scanf("%d",&x);
            if(!q[0].size()||!q[1].size()){
                puts("UNSUCCESS");
            }
            else{
                puts("SUCCESS");
                ll a,b;
                if(tag[0])a=q[0].front(),q[0].pop_front();
                else a=q[0].back(),q[0].pop_back();
                if(tag[1])b=q[1].front(),q[1].pop_front();
                else b=q[1].back(),q[1].pop_back();
                if(tag[f[x]]){
                    q[f[x]].push_front(abs(a-b));
                }
                else{
                    q[f[x]].push_back(abs(a-b));
                }
            }
        }
        else if(k[0]=='D'&&k[1]=='E'){
            scanf("%d",&x);
            puts("SUCCESS");
            tag[f[x]]=0;
            while(q[f[x]].size())q[f[x]].pop_back();
        }
        else if(k[0]=='M'&&k[1]=='O'){
            scanf("%d%d",&x,&y);
            puts("SUCCESS");
            if(q[f[x]].size()<q[f[y]].size()){
                while(q[f[x]].size()){
                    ll a;
                    if(tag[f[x]])a=q[f[x]].front(),q[f[x]].pop_front();
                    else a=q[f[x]].back(),q[f[x]].pop_back();
                    if(tag[f[y]])q[f[y]].push_front(a);
                    else q[f[y]].push_back(a);
                }
                tag[f[y]]^=1;
                swap(f[0],f[1]);
            }
            else{
                while(q[f[y]].size()){
                    ll a;
                    if(tag[f[y]])a=q[f[y]].front(),q[f[y]].pop_front();
                    else a=q[f[y]].back(),q[f[y]].pop_back();
                    if(tag[f[x]])q[f[x]].push_front(a);
                    else q[f[x]].push_back(a);
                }
            }
        }
        else if(k[0]=='S'&&k[1]=='W'){
            swap(f[0],f[1]);puts("SUCCESS");
        }
        else if(k[0]=='E'&&k[1]=='N'){
        	puts("SUCCESS");
            if(!q[f[0]].size())puts("NONE");
            else {
                if(tag[f[0]]){
                    while(q[f[0]].size())
                      printf("%lld ",q[f[0]].front()),q[f[0]].pop_front();
                }
                else{
                    while(q[f[0]].size())
                      printf("%lld ",q[f[0]].back()),q[f[0]].pop_back();
                }
                puts("");
            }
            if(!q[f[1]].size())puts("NONE");
            else {
                if(tag[f[1]]){
                    while(q[f[1]].size())
                      printf("%lld ",q[f[1]].front()),q[f[1]].pop_front();
                }
                else{
                    while(q[f[1]].size())
                      printf("%lld ",q[f[1]].back()),q[f[1]].pop_back();
                }
                puts("");
            }
            break;
        }
    }
    return 0;
}