14097: 【原4097】简单链表

题目

题目描述

author: kikyou 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4097

【试题描述】

给定一个N个数的数组，M次操作，每次操作为下列操作之一。求最后的数组。

操作1：在第X个数之后插入一个数Y。

操作2：删除第X个数。

【输入要求】

第一行两个整数N，M（N，M≤100000）含义见试题描述。

第二行N个整数，表示原来的数组。

接下来M行，每行第一个数OPT，表示操作类型。

对于操作1，接下来两个数X，Y，含义见题面描述，保证0≤X≤当前数的个数，若X=0，表示在数组开头插入。

对于操作2，接下来一个数X，含义见题面描述，保证1≤X≤当前数的个数。

【输出要求】

输出若干个数，表示最后的数组。

【输入样例】

5 3 1 2 3 4 5 1 1 6 2 1 2 2

【输出样例】

6 3 4 5

FineArtz's solution

/* 简单链表 */
#include <iostream>
#include <cmath>
using namespace std;

const int MAXS = 1000;

int n, m, maxs;

class Block{
public:
    Block *prev = nullptr, *next = nullptr;
    int data[MAXS];
    int len = 0;

    Block(Block *p = nullptr, Block *q = nullptr) : prev(p), next(q) {}

    void split(int pos){
        if (pos >= len || pos < 0)
            return;
        Block *b = new Block(this, next);
        if (next != nullptr)
            next->prev = b;
        next = b;
        b->len = len - pos;
        for (int i = 0; i < len - pos; ++i)
            b->data[i] = data[i + pos];
        len = pos;
    }

    bool merge(){
        Block *b = next;
        if (b == nullptr)
            return false;
        if (len + b->len > maxs)
            return false;
        next = b->next;
        if (next != nullptr)
            next->prev = this;
        for (int i = 0; i < b->len; ++i)
            data[len++] = b->data[i];
        delete b;
        return true;
    }

    void delNext(){
        Block *b = next;
        if (b == nullptr)
            return;
        next = b->next;
        if (next != nullptr)
            next->prev = this;
        delete b;
    }
};

ostream &operator <<(ostream &os, const Block &b){
    for (int i = 0; i < b.len; ++i)
        os << b.data[i] << ' ';
    return os;
}

Block *head = new Block();

void insert(int x, int y){
    Block *p = head->next;
    while (p && x > p->len){
        x -= p->len;
        p = p->next;
    }
    p->split(x);
    p->data[p->len++] = y;
}

void remove(int x){
    Block *p = head->next;
    while (p && x > p->len){
        x -= p->len;
        p = p->next;
    }
    p->split(x);
    --p->len;
}

void maintain(){
    Block *p = head->next;
    while (p){
        p->merge();
        p = p->next;
    }
}

int main(){
    cin >> n >> m;
    maxs = (int)(sqrt(n)) + 1;
    Block *p = head->next = new Block();
    for (int i = 1; i <= n; ++i){
        int t;
        cin >> t;
        p->data[p->len++] = t;
        if (p->len == maxs){
            p->next = new Block();
            p = p->next;
        }
    }
    while (m--){
        int op;
        cin >> op;
        if (op == 1){
            int x, y;
            cin >> x >> y;
            insert(x, y);
        }
        else{
            int x;
            cin >> x;
            remove(x);
        }
        maintain();
    }
    p = head->next;
    while (p){
        cout << *p;
        p = p->next;
    }
    cout << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "vector"
#include "cmath"
using namespace std;

template <class T>
class block_node {
public:
    vector<T> val;
    block_node<T>* next = nullptr;
    block_node<T>* last = nullptr;
    size_t len = 0;
};

template <class T>
class block_list {
public:
    block_node<T>* head = nullptr;
    block_node<T>* rear = nullptr;
    size_t _size = 0;

    block_list() {
        head = new block_node<T>;
        rear = new block_node<T>;
        head->next = rear;
        rear->last = head;
        _size = 0;
    }

    //从数组导入
    void from_array(T* array_data, size_t array_size) {
        _size = array_size;
        auto block_size = (size_t)sqrt(array_size);
        auto p = head;
        for (size_t i = 0; i < array_size; i += block_size) {
            p->next = new block_node<T>;
            p->next->last = p;
            p = p->next;
            for (size_t j = 0; j < block_size && i + j < array_size; ++j) {
                p->val.push_back(array_data[i + j]);
                ++p->len;
            }
        }
        p->next = rear;
        rear->last = p;
    }

    //查找
    T& find(unsigned int pos) {
        auto p = head;
        unsigned int i = 0;
        for (; i + p->len <= pos; i += p->len, p = p->next);
        return p->val[pos - i];
    }

    //插入
    void insert(unsigned int pos, const T& val) {
        auto p = head;
        unsigned int i = 0;
        for (; i + p->len <= pos && p->next->next; i += p->len, p = p->next);
        ++p->len;
        ++_size;
        p->val.insert(p->val.begin() + (pos - i), val);
        //判断是否超限
        auto block_size = (size_t)sqrt(_size);
        if (p->len > 2 * block_size) {
            auto temp = new block_node<T>;
            temp->val.assign(p->val.begin() + p->len / 2, p->val.end());
            p->val.erase(p->val.begin() + p->len / 2, p->val.end());
            temp->len = p->len - p->len / 2;
            p->len /= 2;
            p->next->last = temp;
            temp->next = p->next;
            p->next = temp;
            temp->last = p;
        }
    }

    //删除
    void erase(unsigned int pos) {
        auto p = head;
        unsigned int i = 0;
        for (; i + p->len <= pos; i += p->len, p = p->next);
        --p->len;
        --_size;
        p->val.erase(p->val.begin() + (pos - i));
        //判断是否完全删除
        if (p->len <= 0) {
            p->last->next = p->next;
            p->next->last = p->last;
            delete p;
            return;
        }
        //判断是否太小
        auto block_size = (size_t)sqrt(_size);
        if (p->len + p->next->len < block_size && p->next != rear) {
            //合并
            p->val.insert(p->val.end(), p->next->val.begin(), p->next->val.end());
            p->len += p->next->len;
            auto temp = p->next;
            p->next = p->next->next;
            p->next->last = p;
            delete temp;
        }
    }

    //打印
    void println() {
        for (auto p = head; p->next->next; p = p->next)
            for (auto q : p->next->val)
                cout << q << " ";
    }
};

block_list<int> list_data;
int init_array[100009] = { 0 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
        cin >> init_array[i];
    list_data.from_array(init_array, N);

    for (int i = 0; i < M; ++i) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int X, Y;
            cin >> X >> Y;
            list_data.insert(X, Y);
        }
        else {
            int X;
            cin >> X;
            list_data.erase(X - 1);
        }
    }
    list_data.println();
    return 0;
}

q4x3's solution

/**
 * 模拟
 **/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

int dt[100233], N, M, op;

void insert(int x, int y) {
    ++ N;
    for(int i = N;i > x + 1;-- i)
        dt[i] = dt[i - 1];
    dt[x + 1] = y;
}

void del(int x) {
    -- N;
    for(int i = x;i <= N;++ i)
        dt[i] = dt[i + 1];
}

int main() {
    scanf("%d%d", &N, &M);
    for(int i = 1;i <= N;++ i)
        scanf("%d", &dt[i]);
    for(int i = 0;i < M;++ i) {
        scanf("%d", &op);
        if(op == 1) {
            int x, y;
            scanf("%d%d", &x, &y);
            insert(x, y);
        } else {
            int x;
            scanf("%d", &x);
            del(x);
        }
    }
    for(int i = 1;i <= N;++ i)
        printf("%d ", dt[i]);
    printf("\n");
}

victrid's solution

#include <cstdio>
#include <iostream>

#ifndef __CHUCKSIZE__
#define __CHUCKSIZE__ 256
#endif

#ifndef __CHECKVALVE__
#define __CHECKVALVE__ 1
#endif

namespace sjtu {

template <typename T>
class deque {
private:
    struct node {
        T* data;
        node *last, *next;
        node() : data(nullptr), last(nullptr), next(nullptr) {}
        node(node* last, node* next) : data(nullptr), last(last), next(next) {}
        node(const T& data) : last(nullptr), next(nullptr), data(new T(data)) {}
        node(const node& other) : last(nullptr), next(nullptr) {
            if (other.data != nullptr) {
                data = new T(*(other.data));
            } else
                data = nullptr;
        }

        ~node() {
            if (data != nullptr)
                delete data;
        }
    };
    struct block {
        size_t size;
        node *head,
            *tail;
        block *last,
            *next;
        block() : size(0), head(new node()), tail(new node()), last(nullptr), next(nullptr) {
            head->next = tail;
            tail->last = head;
        }
        block(const block& other) : head(new node()), tail(new node()), size(other.size), last(nullptr), next(nullptr) {
            node *nthis = head, *nother = other.head->next, *tmp;
            while (nother != other.tail) {
                tmp         = nthis;
                nthis->next = new node(*nother);
                nthis       = nthis->next;
                nthis->last = tmp;
                nother      = nother->next;
            }
            nthis->next = tail;
            tail->last  = nthis;
        }
        block(size_t size, node* head, node* tail, block* last, block* next) : size(size), head(head), tail(tail), last(last), next(next) {}
        ~block() {
            node* p = head;
            while (p != tail) {
                p = p->next;
                delete p->last;
            }
            delete tail;
        }
        //node and position
        node* no_at(size_t pos) const {
            node* p = head->next;
            while (pos) {
                p = p->next;
                pos--;
            }
            return p;
        }
        T& at(size_t pos) {
            return *(no_at(pos)->data);
        }
        size_t re_at(node* pos) const {
            node* p    = head->next;
            size_t loc = 0;
            while (p != pos) {
                ++loc;
                p = p->next;
            }
            return loc;
        }
        //int to resolve ambiguity
        void insert(const T& _data, node* at, int) {
            at             = at->last;
            node* ins      = new node(_data);
            ins->next      = at->next;
            at->next->last = ins;
            at->next       = ins;
            ins->last      = at;
            ++size;
            return;
        }
        void erase(node* at, int) {
            at       = at->last;
            at->next = at->next->next;
            delete at->next->last;
            at->next->last = at;
            --size;
        }
        void insert(const T& _data, const size_t pos) {
            return insert(_data, no_at(pos), 0);
        }
        void push_back(const T& _data) {
            return insert(_data, tail, 0);
        }
        void pop_back() {
            erase(tail->last, 0);
        }
        void push_front(const T& _data) {
            return insert(_data, 0);
        }
        void pop_front() {
            erase(head->next, 0);
        }

        T& front() const {
            return *(head->next->data);
        }
        T& back() const {
            return *(tail->last->data);
        }
        //Changed _! don't work if end
        //EMPTY_SAFE
        void split(node* pos) {
            node *left_tail, *right_head;
            left_tail        = new node();
            right_head       = new node();
            left_tail->last  = pos;
            right_head->next = pos->next;
            pos->next->last  = right_head;
            pos->next        = left_tail;
            block* ins       = new block(size - this->re_at(pos) - 1, right_head, tail, this, next);
            size             = this->re_at(pos) + 1;
            tail             = left_tail;
            next->last       = ins;
            next             = ins;
        }
        //UNSAFE
        void merge() {
            tail->last->next       = next->head->next;
            tail->last->next->last = tail->last;
            next->head->next       = next->tail;
            tail->last             = next->tail->last;
            tail->last->next       = tail;
            next->tail->last       = next->head;
            size += next->size;
            next = next->next;
            delete next->last;
            next->last = this;
        }
        bool exist(node* pos) const {
            node* rev = pos;
            for (int i = 0; i < (size >> 1) + 3; i++) {
                if (pos == tail || rev == head) {
                    return true;
                }
                if (pos == nullptr || rev == nullptr) {
                    return false;
                }
                pos = pos->next;
                rev = rev->last;
            }
            return false;
        }
    };

private:
    size_t _size;
    block *head, *tail;

    bool Collectable(size_t size) const { return size >= __CHUCKSIZE__ && (size * size >= __CHECKVALVE__ * _size); }
    block* bl_at(size_t& pos) const {
        block* p = head->next;
        while (pos >= p->size) {
            pos -= p->size;
            p = p->next;
        }
        return p;
    }

public:
    class const_iterator;
    class iterator {
        friend class deque;

    private:
        deque* deq;
        block* blk;
        node* pos;

    public:
        iterator() : deq(nullptr), blk(nullptr), pos(nullptr) {}
        iterator(const iterator& other) : deq(other.deq), blk(other.blk), pos(other.pos) {}
        iterator(deque* deq, block* blk, node* pos) : deq(deq), blk(blk), pos(pos) {}
        //Uhh. If problem I'll rewrite +-
        iterator& operator+=(const int& n) {
            if (n == 0)
                return *this;
            if (n < 0)
                return (*this -= (-n));
            size_t dist   = n + blk->re_at(pos);
            block* newblk = blk;
            while (dist >= newblk->size && newblk->next != deq->tail) {
                dist -= newblk->size;
                newblk = newblk->next;
            }
            node* newpos = newblk->head->next;
            while (dist) {
                --dist;
                newpos = newpos->next;
            }
            blk = newblk;
            pos = newpos;
            return *this;
        }
        iterator& operator-=(const int& n) {
            if (n == 0)
                return *this;
            if (n < 0)
                return (*this += (-n));
            int dist      = n - blk->re_at(pos);
            block* newblk = blk;
            while (dist > 0) {
                newblk = newblk->last;
                dist -= newblk->size;
            }
            dist         = -dist;
            node* newpos = newblk->head->next;
            while (dist) {
                --dist;
                newpos = newpos->next;
            }
            blk = newblk;
            pos = newpos;
            return *this;
        }
        iterator operator+(const int& n) const {
            return iterator(*this) += n;
        }
        iterator operator-(const int& n) const {
            return iterator(*this) -= n;
        }
        //DEST
        int operator-(const iterator& rhs) const {
            if (deq != rhs.deq) {
                return -1;
            }
            size_t index = blk->re_at(pos), rindex = rhs.blk->re_at(rhs.pos);
            block *lp = blk, *rp = rhs.blk, *tmp = deq->head->next;
            while (tmp != lp) {
                index += tmp->size;
                tmp = tmp->next;
            }
            tmp = rhs.deq->head->next;
            while (tmp != rp) {
                rindex += tmp->size;
                tmp = tmp->next;
            }
            return index - rindex;
        }
        //++iter
        iterator& operator++() {
            if (blk->next == deq->tail) {
                pos = pos->next;
            } else if (pos->next == blk->tail) {
                blk = blk->next;
                pos = blk->head->next;
            } else {
                pos = pos->next;
            }
            return *this;
        }
        //iter++
        iterator operator++(int) {
            iterator p(*this);
            ++(*this);
            return p;
        }
        //--iter
        iterator& operator--() {
            if (pos->last == blk->head) {
                blk = blk->last;
                pos = blk->tail->last;
            } else {
                pos = pos->last;
            }
            return *this;
        }
        //iter--
        iterator operator--(int) {
            iterator p(*this);
            --(*this);
            return p;
        }

        T& operator*() const {
            return *(pos->data);
        }
        T* operator->() const noexcept {
            return &*(*this);
        }

        bool operator==(const iterator& rhs) const {
            return ((deq == rhs.deq) && (blk == rhs.blk) && (pos == rhs.pos));
        }
        bool operator==(const const_iterator& rhs) const {
            return ((deq == rhs.deq) && (blk == rhs.blk) && (pos == rhs.pos));
        }
        bool operator!=(const iterator& rhs) const {
            return ((deq != rhs.deq) || (blk != rhs.blk) || (pos != rhs.pos));
        }
        bool operator!=(const const_iterator& rhs) const {
            return ((deq != rhs.deq) || (blk != rhs.blk) || (pos != rhs.pos));
        }
    };
    class const_iterator {

    private:
        const deque* deq;
        block* blk;
        node* pos;

    public:
        const_iterator() : deq(nullptr), blk(nullptr), pos(nullptr) {}
        const_iterator(const const_iterator& other) : deq(other.deq), blk(other.blk), pos(other.pos) {}
        const_iterator(const iterator& other) : deq(other.deq), blk(other.blk), pos(other.pos) {}
        const_iterator(const deque* deq, block* blk, node* pos) : deq(deq), blk(blk), pos(pos) {}
        //Uhh. If problem I'll rewrite +-
        const_iterator& operator+=(const int& n) {
            if (n == 0)
                return *this;
            if (n < 0)
                return (*this -= (-n));
            size_t dist   = n + blk->re_at(pos);
            block* newblk = blk;
            while (dist >= newblk->size && newblk->next != deq->tail) {
                dist -= newblk->size;
                newblk = newblk->next;
            }
            node* newpos = newblk->head->next;
            while (dist) {
                --dist;
                newpos = newpos->next;
            }
            blk = newblk;
            pos = newpos;
            return *this;
        }
        const_iterator& operator-=(const int& n) {
            if (n == 0)
                return *this;
            if (n < 0)
                return (*this += (-n));
            int dist      = n - blk->re_at(pos);
            block* newblk = blk;
            while (dist > 0) {
                newblk = newblk->last;
                dist -= newblk->size;
            }
            dist         = -dist;
            node* newpos = newblk->head->next;
            while (dist) {
                --dist;
                newpos = newpos->next;
            }
            blk = newblk;
            pos = newpos;
            return *this;
        }
        const_iterator operator+(const int& n) const {
            return const_iterator(*this) += n;
        }
        const_iterator operator-(const int& n) const {
            return const_iterator(*this) -= n;
        }
        //DIST
        int operator-(const const_iterator& rhs) const {
            size_t index = blk->re_at(pos), rindex = rhs.blk->re_at(rhs.pos);
            block *lp = blk, *rp = rhs.blk, *tmp = deq->head->next;
            while (tmp != lp) {
                index += tmp->size;
                tmp = tmp->next;
            }
            tmp = rhs.deq->head->next;
            while (tmp != rp) {
                rindex += tmp->size;
                tmp = tmp->next;
            }
            return index - rindex;
        }

        const_iterator& operator++() {
            if (blk->next == deq->tail) {
                pos = pos->next;
            } else if (pos->next == blk->tail) {
                blk = blk->next;
                pos = blk->head->next;
            } else {
                pos = pos->next;
            }
            return *this;
        }
        //????Why I use const_ it SEGSIGV?
        const_iterator operator++(int) {
            iterator p(deq, blk, pos);
            ++(*this);
            return p;
        }
        const_iterator& operator--() {
            if (pos->last == blk->head) {
                blk = blk->last;
                pos = blk->tail->last;
            } else {
                pos = pos->last;
            }
            return *this;
        }
        const_iterator operator--(int) {
            iterator p(deq, blk, pos);
            --(*this);
            return p;
        }
        T& operator*() const {
            return *(pos->data);
        }

        T* operator->() const noexcept {
            return &*(*this);
        }

        bool operator==(const iterator& rhs) const {
            return ((deq == rhs.deq) && (blk == rhs.blk) && (pos == rhs.pos));
        }
        bool operator==(const const_iterator& rhs) const {
            return ((deq == rhs.deq) && (blk == rhs.blk) && (pos == rhs.pos));
        }
        bool operator!=(const iterator& rhs) const {
            return ((deq != rhs.deq) || (blk != rhs.blk) || (pos != rhs.pos));
        }
        bool operator!=(const const_iterator& rhs) const {
            return ((deq != rhs.deq) || (blk != rhs.blk) || (pos != rhs.pos));
        }
    };

    deque() : _size(0), head(new block()), tail(new block()) {
        block* first = new block();
        head->next   = first;
        first->last  = head;
        first->next  = tail;
        tail->last   = first;
    }
    deque(const deque& other) : _size(other._size), head(new block()), tail(new block()) {
        block *nthis = head, *nother = other.head->next, *tmp;
        while (nother != other.tail) {
            tmp         = nthis;
            nthis->next = new block(*nother);
            nthis       = nthis->next;
            nthis->last = tmp;
            nother      = nother->next;
        }
        nthis->next = tail;
        tail->last  = nthis;
    }

    ~deque() {
        block* b = head;
        while (b != tail) {
            b = b->next;
            delete b->last;
        }
        delete tail;
    }
    deque& operator=(const deque& other) {
        if (&other == this)
            return *this;
        _size        = other._size;
        block *bthis = head->next, *bother = (other.head)->next, *tmp;
        while (bthis != tail) {
            tmp   = bthis;
            bthis = bthis->next;
            delete tmp;
        }
        bthis = head;
        while (bother != other.tail) {
            tmp         = bthis;
            bthis->next = new block(*bother);
            bthis       = bthis->next;
            bthis->last = tmp;
            bother      = bother->next;
        }
        bthis->next = tail;
        tail->last  = bthis;
        return *this;
    }
    T& at(const size_t& pos) {
        size_t ppos = pos;
        return bl_at(ppos)->at(ppos);
    }
    iterator dq_at(const size_t& pos) {
        if (pos == _size)
            return end();
        size_t ppos = pos;
        block* ats  = bl_at(ppos);
        node* atts  = ats->no_at(ppos);
        return iterator(this, ats, atts);
    }
    const T& at(const size_t& pos) const {
        size_t ppos = pos;
        return bl_at(ppos)->at(ppos);
    }
    T& operator[](const size_t& pos) {
        return at(pos);
    }
    const T& operator[](const size_t& pos) const {
        return at(pos);
    }

    const T& front() const {
        return head->next->front();
    }
    const T& back() const {
        return tail->last->back();
    }

    iterator begin() {
        return iterator(this, head->next, head->next->head->next);
    }
    const_iterator cbegin() const {
        return const_iterator(this, head->next, head->next->head->next);
    }
    iterator end() {
        return iterator(this, tail->last, tail->last->tail);
    }
    const_iterator cend() const {
        return const_iterator(this, tail->last, tail->last->tail);
    }
    bool empty() const { return !_size; }

    size_t size() const { return _size; }

    void clear() {
        _size    = 0;
        block* p = head->next;
        while (p != tail) {
            p = p->next;
            delete p->last;
        }
        head->next       = new block();
        head->next->last = head;
        head->next->next = tail;
        tail->last       = head->next;
    }

    iterator insert(iterator pos, const T& value) {
        pos.blk->insert(value, pos.pos, 0);
        _size++;
        pos = iterator(this, pos.blk, pos.pos->last);
        if (Collectable(pos.blk->size))
            pos.blk->split(pos.pos);
        return pos;
    }
    iterator erase(iterator pos) {
        //lastent illegal iterator
        node* pnext = pos.pos->next;
        pos.blk->erase(pos.pos, 0);
        --_size;
        if (pnext == pos.blk->tail && pos.blk->next != pos.deq->tail) {
            if (pos.blk->next != pos.deq->tail) {
                pos.blk = pos.blk->next;
                pos.pos = pos.blk->head->next;
                return pos;
            } else {
                return end();
            }
        }
        pos.pos = pnext;
        //Here empty is processed.
        if ((pos.blk->next != tail) && (pos.blk->size + pos.blk->next->size <= __CHUCKSIZE__))
            pos.blk->merge();
        return pos;
    }

    void push_back(const T& value) {
        ++_size;
        block* p = tail->last;
        if (Collectable(tail->last->size)) {
            p->next       = new block();
            p->next->last = p;
            p->next->next = tail;
            tail->last    = p->next;
            p->next->push_back(value);
        } else {
            p->push_back(value);
        }
        return;
    }

    void pop_back() {
        --_size;
        tail->last->pop_back();
        if (tail->last->size == 0 && tail->last->last != head) {
            block* del             = tail->last;
            tail->last->last->next = tail;
            tail->last             = tail->last->last;
            delete del;
        }
        return;
    }

    void push_front(const T& value) {
        ++_size;
        block* p = head->next;
        if (Collectable(p->size)) {
            head->next = new block();
            head->next->push_front(value);
            head->next->next       = p;
            head->next->last       = head;
            head->next->next->last = head->next;
        } else {
            p->push_front(value);
        }
    }

    void pop_front() {
        --_size;
        head->next->pop_front();
        if (head->next->size == 0 && tail->last->last != head) {
            block* p         = head->next;
            head->next       = head->next->next;
            head->next->last = head;
            delete p;
            return;
        }
        if ((head->next->next != tail) && ((head->next->size + head->next->next->size) < __CHUCKSIZE__)) {
            head->next->merge();
        }
    }
};

} // namespace sjtu

int main() {
    sjtu::deque<long long> deq;
    int n, m, op;
    long long pc, op1, op2;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &pc);
        deq.push_back(pc);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%lld%lld", &op1, &op2);
            deq.insert(deq.dq_at(op1), op2);
        } else {
            scanf("%lld", &op1);
            deq.erase(deq.dq_at(op1 - 1));
        }
    }
    for (auto it = deq.begin(); it != deq.end(); it++) {
        printf("%lld ", *it);
    }
    return 0;
}