求助块状链表
查看原帖
求助块状链表
394238
Amadeus004楼主2024/1/28 15:11

一开始是8pts+WA

后来调成24pts+RE了,不知道了哪里出了问题,已经尽量合并了

提交记录

调一天调不动了,有没有大佬帮忙

#include<bits/stdc++.h>
#define N 2100005
#define Len 4005
using namespace std;
inline int read(){
	int f=1,tmp=0;
	char a=getchar();
	while(a<'0' or a>'9')f=a=='-'?-f:f,a=getchar();
	while(a>='0' and a<='9')tmp=(tmp<<3)+(tmp<<1)+a-'0',a=getchar();
	return tmp*f;
}
struct Node{
	int siz,tag,nex;
	char blo[Len<<2];
}lis[Len<<4];
int pool[Len<<4],cnt;
inline int New(){return pool[cnt++];}
inline void Clear(int x){pool[--cnt]=x,lis[x].tag=0;}
inline void Init(){
	for(int i=0;i<(Len<<4);i++)pool[i]=i;
	lis[0].nex=-1,cnt=1;
}
inline void Add(int x,int y,int s,char txt[]){
	if(y!=-1){
		lis[y].nex=lis[x].nex,lis[y].siz=s;
		memcpy(lis[y].blo,txt,s);
	}
	lis[x].nex=y;
}
inline void Change(int x){
	lis[x].tag=0;
	reverse(lis[x].blo,lis[x].blo+lis[x].siz);
}
inline void Split(int x,int pos){
	if(x==-1 or pos==lis[x].siz)return;
	if(lis[x].tag)Change(x);
	Add(x,New(),lis[x].siz-pos,lis[x].blo+pos);
	lis[x].siz=pos;
}
inline void Merge(int x,int y){
	if(lis[x].tag)Change(x);
	if(lis[y].tag)Change(y);
	memcpy(lis[x].blo+lis[x].siz,lis[y].blo,lis[y].siz);
	lis[x].siz+=lis[y].siz,lis[x].nex=lis[y].nex;
	Clear(y);
}
inline void Update(int x){for(int i=x;i!=-1;i=lis[i].nex)if(lis[x].nex!=-1 and lis[x].siz+lis[lis[x].nex].siz<=Len)Merge(x,lis[x].nex);}
inline int Get(int &pos){
	int x=0;
	while(x!=-1 and pos>lis[x].siz)pos-=lis[x].siz,x=lis[x].nex;
	return x;
}
inline void Insert(int pos,int s,char txt[]){
	int x=Get(pos);
	Split(x,pos);
	int tmp=0,node;
	while(tmp+Len<=s){
		Add(x,node=New(),Len,txt+tmp);
		tmp+=Len,x=node;
	}
	if(s-tmp)Add(x,node=New(),s-tmp,txt+tmp);
	Update(0);
}
inline void Delete(int pos,int s){
	int x=Get(pos);
	Split(x,pos);
	int nex=lis[x].nex;
	while(nex!=-1 and s>=lis[nex].siz){
		s-=lis[nex].siz;
		Clear(nex);
		nex=lis[nex].nex,lis[x].nex=nex;
	}
	Split(nex,s);
	Clear(nex),lis[x].nex=nex=lis[nex].nex;
	Update(0);
}
inline void Print(int pos){
	int x=Get(pos);
	if(pos==lis[x].siz)x=lis[x].nex,pos=0;
	if(lis[x].tag)Change(x);
	if(lis[x].blo[pos]!='\n')putchar(lis[x].blo[pos]);
	putchar('\n');
}
inline void Reverse(int pos,int s){
	int x=Get(pos);
	Split(x,pos);
	stack<int>st;
	int nex=lis[x].nex;
	while(nex!=-1 and s>=lis[nex].siz)s-=lis[nex].siz,lis[nex].tag^=1,st.push(nex),nex=lis[nex].nex;
	if(nex!=-1 and s){
		Split(nex,s);
		st.push(nex),lis[nex].tag^=1,nex=lis[nex].nex;
	}
	while(st.size()){
		int u=st.top();
		st.pop();
		if(lis[x].siz+lis[u].siz<=Len)Merge(x,u);
		else lis[x].nex=u,x=u;
	}
	lis[x].nex=nex;
	Update(0);
}
int t,m,pos;
char opt[Len],txt[N];
signed main(){
	Init();
	t=read();
	while(t--){
		scanf("%s",opt);
		if(opt[0]=='M')pos=read();
		else if(opt[0]=='G')Print(pos);
		else if(opt[0]=='P')pos--;
		else if(opt[0]=='N')pos++;
		else if(opt[0]=='D'){
			m=read();
			Delete(pos,m);
		}else if(opt[0]=='R'){
			m=read();
			Reverse(pos,m);
		}else if(opt[0]=='I'){
			m=read();
			for(int i=0;i<m;i++){
				txt[i]=getchar();
				while((txt[i]<32 or txt[i]>126) and txt[i]!='\n' and txt[i]!='\r')txt[i]=getchar();
			}
			Insert(pos,m,txt);
		}
	}
	return 0;
}
2024/1/28 15:11
加载中...