真就是入门题啊
by lhs_chris @ 2023-11-01 20:55:11
更新了，现在 70 分，WA on #1,7,8
```cpp
/*
Input:
8
Move 0
Insert 12
-1938rhefids
Insert 13
1145141919810
Move 7
Get 10
Insert 4
asf1
Move 0
Get 15
Output:
919810-193
1145141asf19198
*/
#include<iostream>
#include<cstdio>
using namespace std;
/*==================================================================*/
const int standard=900;
struct Node{
char c;
int bid,prev,next;
}a[4100010];
struct Block{
int sz,beg,prev,next;
}b[20010];
int curpos,begb,enda,endb;
void Split(int bid)
{
int k=b[bid].sz,now=b[bid].beg;
b[bid].sz/=2,endb++;
for(int i=1;i<=k;i++)
{
if(i>k/2)
{
if(i==k/2+1)
{
b[endb].sz=k-k/2,b[endb].beg=now;
b[endb].prev=bid,b[endb].next=b[bid].next;
b[b[bid].next].prev=endb,b[bid].next=endb;
}
a[now].bid=endb;
}
now=a[now].next;
}
}
void Merge(int bid)
{
int bid2=b[bid].next,now=b[bid2].beg;
for(int i=1;i<=b[bid2].sz;i++)
a[now].bid=bid,now=a[now].next;
b[bid].sz+=b[bid2].sz;
b[bid].next=b[bid2].next,b[b[bid2].next].prev=bid;
b[bid2].prev=b[bid2].next=0;
}
int Find(int x)
{
int bid=begb;
while(x>=b[bid].sz&&b[bid].sz)x-=b[bid].sz,bid=b[bid].next;
int now=a[b[bid].beg].prev;
while(x--)
{
if(now)now=a[now].next;
else now=b[begb].beg;
}
return now;
}
void Insert(int x,char c)
{
enda++;
a[enda].c=c;
if(x)a[enda].bid=a[x].bid;
else if(a[x].next)a[enda].bid=a[a[x].next].bid,b[a[enda].bid].beg=enda;
else a[enda].bid=++endb,b[endb].sz=1,b[endb].beg=enda,begb=endb;
a[enda].prev=x,a[enda].next=a[x].next;
a[a[x].next].prev=enda,a[x].next=enda;
if(++b[a[x].bid].sz>=2*standard)Split(a[x].bid);
}
void Delete(int x)
{
int bid=a[x].bid;
a[a[x].prev].next=a[x].next,a[a[x].next].prev=a[x].prev;
a[x].prev=a[x].next=0;
if(--b[bid].sz<standard)
{
if(b[bid].prev&&b[b[bid].prev].sz+b[bid].sz<2*standard)
Merge(b[bid].prev);
else if(b[bid].next&&b[b[bid].next].sz+b[bid].sz<2*standard)
Merge(bid);
}
}
/*==================================================================*/
char read()
{
char c=getchar();
while(c<32||c>126)c=getchar();
return c;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string op;
cin>>op;
if(op=="Move")
{
int x;
scanf("%d",&x);
curpos=Find(x);
}
if(op=="Insert")
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
char c=read();
Insert(curpos,c);
curpos=a[curpos].next;
}
while(n--)curpos=a[curpos].prev;
}
if(op=="Delete")
{
int n;
scanf("%d",&n);
while(n--)
Delete(a[curpos].next);
}
if(op=="Get")
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
curpos=a[curpos].next;
printf("%c",a[curpos].c);
}
printf("\n");
while(n--)curpos=a[curpos].prev;
}
if(op=="Prev")curpos=a[curpos].prev;
if(op=="Next")curpos=a[curpos].next;
}
return 0;
}
```
by Night_sea_64 @ 2023-11-01 21:55:00
已调对，此帖结
by Night_sea_64 @ 2023-11-02 11:40:59