萌新刚学块状链表一秒钟,WA 0pts 求调
查看原帖
萌新刚学块状链表一秒钟,WA 0pts 求调
482610
Mortidesperatslav楼主2024/4/11 19:22
#include<bits/stdc++.h>
using namespace std;
const int sqn = 520;
int cnt, gb, qwq;
struct node{
	public:
		int nxt, siz;
		string vl;
}lis[sqn << 2];
queue<int> q;
int nw(int qq){
	if (!q.empty()){
		int u = q.front();
		q.pop();
		lis[qq].nxt = u;
		lis[u].siz = 0;
		lis[u].vl = "";
		lis[u].nxt = -1; 
		return u;
	}
	lis[qq].nxt = cnt + 1;
	++cnt;
	lis[cnt].siz = 0;
	lis[cnt].vl = "";
	lis[cnt].nxt = -1;
	return cnt;
}
void mg(int u, int v){
	lis[u].vl += lis[v].vl;
	lis[u].nxt = lis[v].nxt;
	lis[u].siz += lis[v].siz;
	lis[v].vl = "";
	lis[v].siz = 0;
	lis[v].nxt = -1;
	q.push(v);
}
void spt(int u, int k){
	int unx = lis[u].nxt;
	int nid = nw(u);
	string s1, s2;
	for (int i = 1; i <= k; i++)
		s1 += lis[u].vl[i];
	for (int i = k + 1; i <= lis[u].siz; i++)
		s2 += lis[u].vl[i];
	lis[u].vl = (string)" " + s1;
	lis[nid].vl = (string)" " + s2;
	lis[u].siz = s1.size();
	lis[nid].siz = s2.size();
	lis[nid].nxt = unx;
}
string gst(int s_siz){
	string res;
	char ch;
	for (int i = 1; i <= s_siz; i++){
		ch = getchar();
		if (ch == '\n'){
			i--;
			continue;
		}
		res += ch;
	}
	return res;
}
void ins(int u, string x){
	if (q.size() >= cnt){
		int v = nw(0);
		lis[v].vl = " " + x;
	}
	int qz = 0, pre = 0;
	for (int v = 0; v != -1; v = lis[v].nxt){
		if (qz < u && qz + lis[v].siz >= u){
			spt(v, u);
			lis[v].vl += x;
			lis[v].siz += x.size();
			if (lis[pre].siz < lis[lis[v].nxt].siz)
				if (lis[v].siz + lis[pre].siz < sqn / 3 * 4)
					mg(pre, v);
			else
				if (lis[v].siz + lis[lis[v].nxt].siz < sqn / 3 * 4)
					mg(v, lis[v].nxt);
			return;
		}
		qz += lis[v].siz;
		pre = v;
	}
}
void bdel(int u, int pre){
	lis[pre].nxt = lis[u].nxt;
	lis[u].vl = "";
	lis[u].siz = 0;
	q.push(u);
}
void del(int l, int r){
	int qz = 0, pre = 0;
	for (int v = 0; v != -1; v = lis[v].nxt){
		int kr = qz + lis[v].siz;
		if (qz >= l && kr <= r)
			bdel(v, pre);
		else{
			if (qz < l){
				string nvl = " ";
				for (int i = l; i <= kr; i++)
					nvl += lis[v].vl[i];
				lis[v].vl = nvl;
				lis[v].siz = lis[v].vl.size();
			}else{
				string nvl = " ";
				for (int i = qz; i <= r; i++)
					nvl += lis[v].vl[i];
				lis[v].vl = nvl;
				lis[v].siz = lis[v].vl.size();
			}
			if (lis[pre].siz < lis[lis[v].nxt].siz)
				if (lis[v].siz + lis[pre].siz < sqn / 3 * 4)
					mg(pre, v);
			else
				if (lis[v].siz + lis[lis[v].nxt].siz < sqn / 3 * 4)
					mg(v, lis[v].nxt);
		}
		pre = v;
	}
}
void get(int l, int r){
	int qz = 0, pre = 0;
	for (int v = 0; v != -1; v = lis[v].nxt){
		int kr = qz + lis[v].siz;
		if (qz >= l && kr <= r)
			for (int i = 1; i <= lis[v].siz; i++)
				cout << lis[v].vl[i];
		else{
			if (qz < l)
				for (int i = l; i <= kr; i++)
					cout << lis[v].vl[i];
			else
				for (int i = qz; i <= r; i++)
					cout << lis[v].vl[i];
		}
	}
}
int main(){
	cin >> qwq;
	while (qwq--){
		string op;
		cin >> op;
		if (op == "Insert"){
			int lnt;
			cin >> lnt;
			ins(gb, gst(lnt));
		}else if (op == "Delete"){
			int x;
			cin >> x;
			del(gb, gb + x);
		}else if (op == "Get"){
			int x;
			cin >> x;
			get(gb, gb + x);
			cout << "\n";		
		}else if (op == "Move"){
			int x;
			cin >> x;
			gb = x;
		}else if (op == "Prev")
			gb--;
		else if (op == "Next")
			gb++;
	}
}
2024/4/11 19:22
加载中...