求助块链
查看原帖
求助块链
105833
樱洛CHANGE楼主2021/7/1 17:46

如样例,在第六行的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的串会进入函数。。。

2021/7/1 17:46
加载中...