如样例,在第六行的delete出现问题。
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
#include<bits/stdc++.h>
#define awa 2147483647
#define zhale exit(0)
#define re register
#define rint re int
using namespace std;
/*Shioiri Kukuri*/
typedef long long ll;
typedef unsigned long long ull;
typedef double qwq;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;
#define rll re ll
/*あなたのためなら、例え命が枯れ果てても--泣き続けてあげるわ*/
template<class T>
void Swap(T &x,T &y)
{
T z=x;
x=y;
y=z;
}
template<class T>
T Read()
{
T x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int (*read)()=Read<int>;
ll (*readll)()=Read<ll>;
const int N=2e3+5,M=1024*1034*2+5;
int m,curpos;
char ans[M];
namespace BlockList{
class Node{
public:
int nxt,sz;
char a[N<<1];
}b[N<<2];
int pool[N<<2],top;
inline int New(){
return pool[++top];
}
inline void Del(int x){
pool[top--]=x;
}
inline void Init(){
for(int i=1;i<(N<<2);++i)
pool[i]=i;
b[0].nxt=-1;
b[0].sz=0;
}
inline void Merge(int x,int y){
memcpy(b[x].a+b[x].sz,b[y].a,b[y].sz);
b[x].sz+=b[y].sz,b[x].nxt=b[y].nxt;
Del(y);
}
inline void Maintain(int st){
for(int blkpos=st,nxt=b[st].nxt;~blkpos;blkpos=b[blkpos].nxt,nxt=b[blkpos].nxt)
while((~nxt)&&b[blkpos].sz+b[nxt].sz<=N)
Merge(blkpos,nxt),nxt=b[blkpos].nxt;
}
inline void add(int x,int y,int len,char c[]){
if(~y){
b[y].nxt=b[x].nxt,b[y].sz=len;
//puts("!");
//cout<<len<<endl;
memcpy(b[y].a,c,len);
}
b[x].nxt=y;
}
inline void Split(int blkpos,int numpos){
if((~blkpos)||numpos==b[blkpos].sz) return ;
//cout<<b[blkpos].sz<<endl;
add(blkpos,New(),b[blkpos].sz-numpos,b[blkpos].a+numpos);
b[blkpos].sz=numpos;
}
inline void Getpos(int &blkpos,int &numpos){
while((~blkpos)&&numpos>b[blkpos].sz)
numpos-=b[blkpos].sz,blkpos=b[blkpos].nxt;
}
inline void Insert(int numpos,int len,char c[]){
int blkpos=0;
Getpos(blkpos,numpos);
Split(blkpos,numpos);
int nowlen=0,newblk,start=blkpos;
while(nowlen+N<=len){
newblk=New();
add(blkpos,newblk,N,c+nowlen);
nowlen+=N;
blkpos=newblk;
}
if(len-nowlen)
newblk=New(),add(blkpos,newblk,len-nowlen,c+nowlen);
//Maintain(0);
if(b[blkpos].sz+b[newblk].sz<=N&&(~newblk))
Merge(blkpos,newblk);
if(b[start].sz+b[b[start].nxt].sz<N&&(~b[start].nxt))
Merge(start,b[start].nxt);
}
inline void Delete(int numpos,int len){
int blkpos=0;
Getpos(blkpos,numpos);
Split(blkpos,numpos);
int nxt=b[blkpos].nxt;
while((~nxt)&&len>b[nxt].sz)
len-=b[nxt].sz,Del(nxt),nxt=b[nxt].nxt;
// len-=b[nxt].sz,nxt=b[nxt].nxt;
Split(nxt,len);
// nxt=b[nxt].nxt;
// for(int i=b[blkpos].nxt;i!=nxt;i=b[blkpos].nxt)
// b[blkpos].nxt=b[i].nxt,Del(i);
// while(b[blkpos].sz+b[nxt].sz<N&&(~nxt))
// Merge(blkpos,nxt),nxt=b[blkpos].nxt;
b[blkpos].nxt=b[nxt].nxt;
Del(nxt);
Maintain(0);
}
inline void Chuans(int numpos,int len){
int blkpos=0;
Getpos(blkpos,numpos);
int nowlen=b[blkpos].sz-numpos;
if(len<nowlen)
nowlen=len;
memcpy(ans,b[blkpos].a+numpos,nowlen);
int nowblk=b[blkpos].nxt;
while((~nowblk)&&len>=nowlen+b[nowblk].sz){
memcpy(ans+nowlen,b[nowblk].a,b[nowblk].sz);
nowlen+=b[nowblk].sz,nowblk=b[nowblk].nxt;
}
if(len-nowlen&&(~nowblk))
memcpy(ans+nowlen,b[nowblk].a,len-nowlen);
ans[len]='\0';
printf("%s\n",ans);
}
}
using namespace BlockList;
inline int True()
{
//#define Freopen
//#define Clock
#ifdef Freopen
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef Clock
rint STR=clock();
#endif
Init();
m=read();
while(m--)
{
char op[6];
scanf("%s",op);
switch(op[0])
{
case 'M':{
curpos=read();
break;
}
case 'I':{
int len=read();
for(int i=0;i<len;++i)
{
ans[i]=getchar();
if(ans[i]<32||ans[i]>126)
i--;
}
Insert(curpos,len,ans);
break;
}
case 'D':{
int len=read();
Delete(curpos,len);
break;
}
case 'G':{
int len=read();
Chuans(curpos,len);
break;
}
case 'P':{
curpos--;
break;
}
case 'N':{
curpos++;
break;
}
}
}
#ifdef Clock
rint END=clock();
printf("Time:%dms\n",int((END-STR)/(qwq)CLOCKS_PER_SEC*1000));
printf("Time:%ds\n",int((END-STR)/(qwq)CLOCKS_PER_SEC));
#endif
return (0-0);//q(0-0)p q(>-<)p
}
int Love=True();
signed main(){;}
代码中Split函数中的b[blkpos].sz=0,所以导致add传入了一个负数的len导致RE。。。
但是现在百思不得其解为什么一个长度为0的串会进入函数。。。