题解 | #简单的数据结构#

题目描述

简单来说，就是需要维护一个容器，支持从前面或后面进行插入、删除元素，能将整个容器翻转，并能对容器中的元素排序。

解题思路

很显然一个双端队列能支持以上所有操作。然而我脑子一抽就想用数组模拟一下，用数组模拟的唯一难点就是翻转数组不好操作，因为头和尾会随意转换，其实可以用reverse()函数直接翻转，但是我又脑子一抽没有想起来，所以用一个 来记录当前的数组是正的还是反的，如果翻转就令 异或 即可。然后又用了一些小技巧省去了繁琐的 ，如此一来，这篇奇怪的题解就诞生了，算是一种别样的思路，仅供参考。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 500010;

int n, m;
int q[N], hh[2];

int main()
{
    cin >> n >> m;
    
    hh[0] = 250001, hh[1] = 250000;
    int t = 0;
    for(int i = 0; i < m; i++)
    {
        int op, x;
        cin >> op;
        if(op == 1)
        {
            cin >> x;
            hh[t] += (t == 1) - (t == 0);
            q[hh[t]] = x;
        }
        else if(op == 2)
            hh[t] -= (t == 1) - (t == 0);
        else if(op == 3)
        {
            cin >> x;
            hh[t ^ 1] += ((t ^ 1) == 1) - ((t ^ 1) == 0);
            q[hh[t ^ 1]] = x;
        }
        else if(op == 4)
            hh[t ^ 1] -= ((t ^ 1) == 1) - ((t ^ 1) == 0);
        else if(op == 5) t ^= 1;
        else if(op == 6)
        {
            cout << hh[1] - hh[0] + 1 << endl;
            if(t == 0)
                for(int i = hh[0]; i <= hh[1]; i++) cout << q[i] << (i < hh[1] ? " " : "");
            else
                for(int i = hh[1]; i >= hh[0]; i--) cout << q[i] << (i > hh[0] ? " " : "");
            cout << endl;
        }
        else
        {
            if(t == 0) sort(q + hh[0], q + hh[1] + 1);
            else sort(q + hh[0], q + hh[1] + 1, greater<int>());
        }
    }
    return 0;
}