14097: 【原4097】简单链表

题目描述

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

【输入样例】

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;
}

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

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

void maintain(){
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();
}
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>* rear = nullptr;
size_t _size = 0;

block_list() {
rear = new block_node<T>;
_size = 0;
}

//从数组导入
void from_array(T* array_data, size_t array_size) {
_size = array_size;
auto block_size = (size_t)sqrt(array_size);
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) {
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) {
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) {
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;
*tail;
block *last,
*next;
block() : size(0), head(new node()), tail(new node()), last(nullptr), next(nullptr) {
}
block(const block& other) : head(new node()), tail(new node()), size(other.size), last(nullptr), next(nullptr) {
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() {
while (p != tail) {
p = p->next;
delete p->last;
}
delete tail;
}
//node and position
node* no_at(size_t pos) const {
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 {
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() {
}

T& front() const {
}
T& back() const {
return *(tail->last->data);
}
//Changed _! don't work if end
//EMPTY_SAFE
void split(node* pos) {
left_tail        = new node();
left_tail->last  = pos;
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->last = tail->last;
tail->last             = next->tail->last;
tail->last->next       = tail;
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;

bool Collectable(size_t size) const { return size >= __CHUCKSIZE__ && (size * size >= __CHECKVALVE__ * _size); }
block* bl_at(size_t& pos) const {
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;
}
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;
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;
}
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;
} else {
pos = pos->next;
}
return *this;
}
//iter++
iterator operator++(int) {
iterator p(*this);
++(*this);
return p;
}
//--iter
iterator& operator--() {
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;
}
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;
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;
}
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;
} 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--() {
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();
first->next  = tail;
tail->last   = first;
}
deque(const deque& other) : _size(other._size), head(new block()), tail(new block()) {
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() {
while (b != tail) {
b = b->next;
delete b->last;
}
delete tail;
}
deque& operator=(const deque& other) {
if (&other == this)
return *this;
_size        = other._size;
while (bthis != tail) {
tmp   = bthis;
bthis = bthis->next;
delete tmp;
}
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 {
}
const T& back() const {
return tail->last->back();
}

iterator begin() {
}
const_iterator cbegin() const {
}
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;
while (p != tail) {
p = p->next;
delete p->last;
}
}

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;
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;
if (Collectable(p->size)) {
} else {
p->push_front(value);
}
}

void pop_front() {
--_size;
delete p;
return;
}
}
}
};

} // 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;
}
``````