NC14661 简单的数据结构 双端队列deque

比较简单的队列模拟题,如果翻转和排序操作出现概率和其他5种一样的话我就不会写了,

• 翻转并不用真的去翻转,可以添加一个翻转标记,偶数次翻转相当于没翻转
• 当为真时,插头变成插尾,删头变成删尾,逆序排序
• 当为假时,正常插头插尾,正常删头删尾,正序排序

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \
do { \
    cout << "\033[31;1m " << #x << " -> "; \
    err(x); \
} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
    template <typename T>
    void read(T& x) {
        int f = 1; x = 0;
        char ch = getchar();

        while (ch < '0' || ch > '9') 
            { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') 
            { x = x * 10 + ch - '0'; ch = getchar(); }
        x *= f;
    }
};
using namespace FIO;
#endif


int n, m, Q, K, rev, lef=MAXN, rig=MAXN-1, que[MAXN<<2];
#define PUSH_BACK(x) (que[++rig] = x)
#define PUSH_FRONT(x) (que[--lef] = x)
#define POP_BACK (rig = lef < rig ? --rig : rig)
#define POP_FRONT (lef = lef < rig ? ++lef : lef)

void push_front(int x) {
    if(rev) //已经翻转
        PUSH_BACK(x);
    else 
        PUSH_FRONT(x);
}

void push_back(int x) {
    if(rev) //已经翻转
        PUSH_FRONT(x);
    else
        PUSH_BACK(x);
}

void pop_front() {
    if(rev) //已经翻转
        POP_BACK;
    else
        POP_FRONT;
}

void pop_back() {
    if(rev) //已经翻转
        POP_FRONT;
    else
        POP_BACK;
}

void output() {
//    forarr(que, lef, rig);
    printf("%d\n", rig-lef+1);
    if(rev) {
        for(int i=rig; i>=lef; i--) 
            printf("%d%c", que[i], i==lef?'\n':' ');
    } else {
        for(int i=lef; i<=rig; i++) 
            printf("%d%c", que[i], i==rig?'\n':' ');
    }
}

void trysort() {
    if(lef > rig) return ;
    if(rev) {
        //翻转的话要逆序排序
        sort(que+lef, que+lef+(rig-lef+1), greater<int>());
    } else {
        sort(que+lef, que+lef+(rig-lef+1));
    }
}

int main() {
#ifdef debug
    freopen("test", "r", stdin);
    clock_t stime = clock();
#endif
    read(n), read(Q);
    int op, x;
    while(Q--) {
        read(op);
        if(op == 1) {
            read(x);
            push_front(x);
        } else if(op == 2) {
            pop_front();
        } else if(op == 3) {
            read(x);
            push_back(x);
        } else if(op == 4) {
            pop_back();
        } else if(op == 5) {
            rev = !rev;
        } else if(op == 6) {
            output();
        } else if(op == 7) {
            trysort();
        }  
    }





#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
    return 0;
}