破防了,块状链表爆0几乎全RE
查看原帖
破防了,块状链表爆0几乎全RE
291939
lihuazou楼主2021/5/27 17:02
//求助下为什么RE,我个人认为没有越界(雾)
//块状链表交了近10发233,结果暴力过了?
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>

const int N = 1e6 + 100;
const int sqn = 1024;

int cnt, sign = sqn << 1;

struct node {
	int sz;
	node* nxt;
	char buff[(sqn << 1) + 5];
	node() { this->sz = 0; this->nxt = NULL; }
	void push(char ch) { buff[++sz] = ch; }
}*root = NULL;

inline void read(std::string& str, int maxlen) {
	int len = 0;
	while (len < maxlen) {
		char ch = std::getchar();
		if (ch >= 32 && ch <= 126) str.push_back(ch), len++;
	}
}

inline void split(node* p) {
	if (p->sz >= sign) {
		node* tp = new node();
		for (int i = sqn + 1; i <= p->sz; i++) tp->push(p->buff[i]);
		p->sz = sqn;
		tp->nxt = p->nxt;
		p->nxt = tp;
		p = p->nxt;
	}
}

inline void op_insert(int pos, int len, std::string str) {
	node* p = root;
	if (pos > cnt) {
		while (p->nxt != NULL) p = p->nxt;
		for (int i = 0; i < len; i++) {
			p->push(str[i]);
			split(p);
		}
		return;
	}
	int tot = p->sz;
	while (tot < pos && p != NULL) {
		p = p->nxt;
		tot += p->sz;
	}
	tot = tot - (p->sz);
	pos = pos - tot;
	node* np = new node();
	for (int i = pos; i <= p->sz; i++) np->push(p->buff[i]);
	p->sz = pos - 1;
	for (int i = 0; i < len; i++) {
		p->push(str[i]);
		split(p);
	}
	for (int i = 1; i <= np->sz; i++) {
		p->push(np->buff[i]);
		split(p);
	}
}

inline void op_delete(int pos, int len) {
	node* p = root;
	int tot = p->sz;
	while (tot < pos && p != NULL) {
		p = p->nxt;
		tot += p->sz;
	}
	tot = tot - (p->sz);
	pos = pos - tot;
	len = len - (p->sz - pos + 1);
	node* np = new node();
	if (len > 0) {
		p->sz = pos - 1;
		node* tp = p->nxt;
		while (len > tp->sz) {
			len -= tp->sz;
			tp = tp->nxt;
		}
		for (int i = len + 1; i <= tp->sz; i++) np->push(tp->buff[i]);
		np->nxt = tp->nxt;
		p->nxt = np;
		return;
	}
	for (int i = pos + len; i <= p->sz; i++) np->push(p->buff[i]);
	p->sz = pos - 1;
	for (int i = 1; i <= np->sz; i++) {
		p->push(np->buff[i]);
		split(p);
	}
}

inline void op_query(int pos, int len) {
	node* p = root;
	int tot = p->sz;
	while (tot < pos && p != NULL) {
		p = p->nxt;
		tot += p->sz;
	}
	tot = tot - (p->sz);
	pos = pos - tot;
	while (len--) {
		while (pos > p->sz) p = p->nxt, pos = 1;
		std::cout << p->buff[pos];
		pos++;
	}
	std::cout << std::endl;
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int n, pos = 0;
	root = new node();
	std::cin >> n;
	while (n--) {
		std::string op;
		std::cin >> op;
		if (op == "Insert") {
			int len;
			std::string str;
			std::cin >> len;
			read(str, len);
			op_insert(pos + 1, len, str);
			cnt += str.length();
		}
		else if (op == "Move") {
			std::cin >> pos;
		}
		else if (op == "Delete") {
			int len;
			std::cin >> len;
			op_delete(pos + 1, len);
			cnt -= len;
		}
		else if (op == "Get") {
			int len;
			std::cin >> len;
			op_query(pos + 1, len);
		}
		else if (op == "Prev") {
			if (pos) pos--;
		}
		else if (op == "Next") {
			if (pos < cnt) pos++;
		}
	}
}
2021/5/27 17:02
加载中...