关于块状链表的删除操作

P4008 [NOI2003] 文本编辑器

似乎是这组数据的问题 ```cpp 5 Insert 5 abcde Move 2 Delete 2 Move 0 Get 3 ```
by CEFqwq @ 2024-04-13 12:54:08


@[爱肝大模拟的tlxjy](/user/482610) 如果插入的字符串的长度大于块长应该分裂,但是你没有做这件事。
by 听取MLE声一片 @ 2024-04-13 12:59:05


我是说你的插入。
by 听取MLE声一片 @ 2024-04-13 12:59:27


@[听取MLE声一片](/user/253738) 这是 TLE 的原因,但是我 WA 貌似是因为删除操作/yun 因为似乎是删除操作后出现了问题
by CEFqwq @ 2024-04-13 13:00:53


@[听取MLE声一片](/user/253738) 但是加上分裂不 MLE 了,变成了 TLE+WA+AC/yiw 我的代码怎么这么逆天啊( 不分裂不是应该会导致块长过大然后时间复杂度大于 $O(\sqrt{n})$ 吗/yun
by CEFqwq @ 2024-04-13 13:13:49


@[小粉兔](/user/10703) 兔队我查出来为什么 WA 了,但是没改对( 我 del 操作写的漏洞百出,目前查出来: 1. l 和 r 没有转化成块内下标 2. 删除之后没有维护元素在原序列中的下标导致重复删 目前我在解决第二个问题/yun
by CEFqwq @ 2024-04-13 14:14:33


现在改成了这样,但是样例没输出了 ```cpp 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 (kr < l){ pre = v; qz += lis[v].siz; continue; } if (qz >= r) break; // cout << v << " " << qz << " " << kr << " " << lis[v].nxt << "\n"; // system("pause"); if (qz >= l && kr <= r){ qz += lis[v].siz; bdel(v, pre); }else{ if (qz < l && kr > r){ spt(v, l - qz - 1); spt(lis[v].nxt, r - qz - lis[v].siz); qz += r - l + 1; bdel(lis[v].nxt, v); }else if (qz < l){ qz += l - qz; spt(v, l - qz - 1); bdel(lis[v].nxt, v); }else{ qz += r - qz + 1; spt(v, r - qz); bdel(v, pre); } if (pre != 0 && lis[pre].siz < lis[lis[v].nxt].siz) if (lis[v].siz + lis[pre].siz < sqn) mg(pre, v); else if (lis[v].nxt != -1) if (lis[v].siz + lis[lis[v].nxt].siz < sqn) mg(v, lis[v].nxt); } pre = v; qz += lis[v].siz; // cout << qz << "\n"; } } ```
by CEFqwq @ 2024-04-13 14:18:11


@[爱肝大模拟的tlxjy](/user/482610) https://www.luogu.com.cn/paste/vor1kj6f 以及我在 UOJ 群里的聊天记录 你爬楼不方便的话,加我好友,我可以打包转发
by 小粉兔 @ 2024-04-13 16:13:26


@[小粉兔](/user/10703) 兔队人真好/bx 回家我就把 CSP-S2020 第一轮讲解循环播放 +154 遍/bx/bx/bx
by CEFqwq @ 2024-04-13 16:15:45


|