HDU 4286 Data Handler[スタック、両端キュー]

分析転入:http://www.haogongju.net/art/1647260
この問題で考えやすいやり方はsplayですが、splayは書くのが面倒で、操作のたびにLogNの複雑さがあり、双方向チェーンテーブルも実現できますが、実践するのは面倒です.特に反転操作です.
毎回LまたはRが1ビット移動していることがわかり、反転操作に関連するため、2つのスタックでLの左側とRの右側のデータをそれぞれ格納し、LとRの中間のデータは1つの両端キューを使用して保存することができます.現在の両端キューのどちらが先頭で、どちらが末尾であるかを1つのdirで表すためです.
タイトルで与えられた7つの操作は,いずれもO(1)の複雑さで実現できるが,説明の便宜上,左スタックはLの左の数のスタックを表し,右スタックはRの右の数のスタックを表す.
1,MoveLeft L/R左シフト左ポインタは,左スタックのスタックトップの数を両端キューヘッダに弾き,左シフト右ポインタはキュー末尾の要素を右スタックに置く.
2,MoveRight L/R右シフト左ポインタはキューヘッダ要素を左スタックに配置し,右シフト右ポインタは右スタックトップ要素を両端キューの末尾に弾く.
3,Insert L Xがキューヘッダに挿入されます.
4,Insert R Xがキューの最後に挿入されます.
5,Delete Lキューヘッダ要素を削除します.
6,Delete Rキューの末尾要素を削除します.
　　7,Reverse　　　　dir^=1.
Code 1(両端キュー、スタックを配列でシミュレート):

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define LL long long
#define pb push_back
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1000005;

int cas,n,m,x[maxn],l,r;
int dq[maxn*2],head,tail;
int stkl[maxn],stkr[maxn];
char s1[20],s2[20];
int dir,topl,topr;

void init(){
    topl=topr=dir=0;
    head=maxn; tail=maxn-1;
    for(int i=1;i<l;i++) stkl[++topl]=x[i];
    for(int i=l;i<=r;i++) dq[++tail]=x[i];
    for(int i=n;i>r;i--) stkr[++topr]=x[i];
}

void MoveLR(char op,char c){
    if(op=='L'&&c=='L'){
        if(!dir) dq[--head]=stkl[topl--];
        else     dq[++tail]=stkl[topl--];
    }
    else if(op=='R'&&c=='L'){
        if(!dir) stkl[++topl]=dq[head++];
        else     stkl[++topl]=dq[tail--];
    }
    else if(op=='L'&&c=='R'){
        if(!dir) stkr[++topr]=dq[tail--];
        else     stkr[++topr]=dq[head++];
    }
    else {
        if(!dir) dq[++tail]=stkr[topr--];
        else     dq[--head]=stkr[topr--];
    }
}

void Insert(char c){
    int num;
    scanf("%d",&num);
    if(c=='L') {
        if(!dir) dq[--head]=num;
        else     dq[++tail]=num;
    }
    else {
        if(!dir) dq[++tail]=num;
        else     dq[--head]=num;
    }
}

void Delete(char c){
    if(c=='L'){
        if(!dir) head++;
        else     tail--;
    }
    else {
        if(!dir) tail--;
        else head++;
    }
}

void Reverse(){
    dir^=1;
}

void print(){
    int cnt=0;
    for(int i=1;i<=topl;i++) x[++cnt]=stkl[i];
    if(!dir) for(int i=head;i<=tail;i++) x[++cnt]=dq[i];
    else     for(int i=tail;i>=head;i--) x[++cnt]=dq[i];
    for(int i=topr;i>0;i--) x[++cnt]=stkr[i];
    for(int i=1;i<cnt;i++) printf("%d ",x[i]); printf("%d
",x[cnt]);
}

int main()
{
    scanf("%d",&cas);
    while(cas--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&x[i]);
        scanf("%d %d %d",&l,&r,&m);
        init();
        while(m--){
            scanf("%s",s1);
            if(s1[0]!='R') scanf("%s",s2);
            switch(s1[0]){
                case 'M':MoveLR(s1[4],s2[0]);break;
                case 'I':Insert(s2[0]);break;
                case 'D':Delete(s2[0]);break;
                case 'R':Reverse();break;
            }
        }
        print();
    }
    return 0;
}

Code 2(C++STL dequeで実現):

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define LL long long
#define pb push_back
#define pf push_front
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1000005;

deque<int>a,b,c;
char s1[20],s2[20];
int num[maxn],n,m,dir,cas,l,r;

void init(){
    dir=0;
    a.clear(); b.clear(); c.clear();
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    scanf("%d %d %d",&l,&r,&m);
    for(int i=1;i<l;i++) a.pb(num[i]);
    for(int i=l;i<=r;i++) b.pb(num[i]);
    for(int i=r+1;i<=n;i++) c.pb(num[i]);
}

void MoveLR(char op,char ch){
    if(op=='L'&&ch=='L'){
        if(!dir) b.pf(*a.rbegin());
        else     b.pb(*a.rbegin());
        a.pop_back();
    }
    else if(op=='R'&&ch=='L'){
        if(!dir) a.pb(*b.begin()),b.pop_front();
        else     a.pb(*b.rbegin()),b.pop_back();
    }
    else if(op=='L'&&ch=='R'){
        if(!dir) c.pf(*b.rbegin()),b.pop_back();
        else     c.pf(*b.begin()),b.pop_front();
    }
    else {
        if(!dir) b.pb(*c.begin());
        else     b.pf(*c.begin());
        c.pop_front();
    }
}

void Insert(char ch){
    int v;
    scanf("%d",&v);
    if(ch=='L') {
        if(!dir) b.pf(v);
        else     b.pb(v);
    }
    else if(ch=='R'){
        if(!dir) b.pb(v);
        else     b.pf(v);
    }
}

void Delete(char ch){
    if(ch=='L'){
        if(!dir) b.pop_front();
        else     b.pop_back();
    }
    else {
        if(!dir) b.pop_back();
        else     b.pop_front();
    }
}

void Reverse(){
    dir^=1;
}

void print(){
    int cnt=0;
    deque<int>::iterator it;
    deque<int>::reverse_iterator rit;
    for(it=a.begin();it!=a.end();it++) num[++cnt]=*it;
    if(!dir) for(it=b.begin();it!=b.end();it++) num[++cnt]=*it;
    else for(rit=b.rbegin();rit!=b.rend();rit++) num[++cnt]=*rit;
    for(it=c.begin();it!=c.end();it++) num[++cnt]=*it;
    for(int i=1;i<cnt;i++) printf("%d ",num[i]); printf("%d
",num[cnt]);
}

int main()
{
    scanf("%d",&cas);
    while(cas--){
        init();
        while(m--){
            scanf("%s",s1);
            if(s1[0]!='R') scanf("%s",s2);
            switch(s1[0]){
                case 'M':MoveLR(s1[4],s2[0]);break;
                case 'I':Insert(s2[0]);break;
                case 'D':Delete(s2[0]);break;
                case 'R':Reverse();break;
             }
        }
        print();
    }
    return 0;
}