FHQ 0pts求条
查看原帖
FHQ 0pts求条
1457824
__assassin_楼主2025/7/3 10:32
#include<bits/stdc++.h>
using namespace std;
const int N=5e6;
struct Node{
	int ls,rs;
	char x;
	int p;
	int size;
	int tag;
}t[N+10];
int root,cnt,n,w;
stack<int> st;
void newNode(char x){
	cnt++;
	t[cnt].ls=0;
	t[cnt].rs=0;
	t[cnt].x=x;
	t[cnt].p=rand();
	t[cnt].size=1;
	t[cnt].tag=0;
}
void Updata(int u){
	t[u].size=t[t[u].ls].size+1+t[t[u].rs].size;
}
void push_down(int u){
	if(t[u].tag){
		swap(t[u].ls,t[u].rs);
		t[t[u].ls].tag^=1;
		t[t[u].rs].tag^=1;
		t[u].tag=0;
	}
}
void Spilt(int u,int k,int &L,int &R){
	if(u==0){
		L=R=0;
		return;
	}
	push_down(u);
	if(t[t[u].ls].size+1<=k){
		L=u;
		Spilt(t[L].rs,k-t[t[L].ls].size-1,t[L].rs,R);
	}
	else{
		R=u;
		Spilt(t[R].ls,k,L,t[R].ls);
	}
	Updata(u);
}
int Merge(int L,int R){
	if(L==0||R==0) return L+R;
	if(t[L].p>=t[R].p){
		push_down(L);
		t[L].rs=Merge(t[L].rs,R);
		Updata(L);
		return L;
	}
	else{
		push_down(R);
		t[R].ls=Merge(L,t[R].ls);
		Updata(R);
		return R;
	}
}
int build(int len){
	char c;
	int last=0;
	while(len){
		c=getchar();
//		if(c=='\n'||c=='\r') continue;
		len--;
		newNode(c);
		last=0;
		while(st.size()&&t[st.top()].p>=t[cnt].p){
			last=st.top();
			Updata(last);
			st.pop();
		}
		if(st.size()){
			t[st.top()].rs=cnt;
		}																		
		t[cnt].ls=last;
		st.push(cnt);
	}
	while(st.size()){
		last=st.top();
		Updata(last);
		st.pop();
	}
	return last;
}
void Move(int k){
	w=k;
}
void Insert(int len){
	int L,R;
	Spilt(root,w,L,R);
	root=Merge(Merge(L,build(len)),R);
}
void Delete(int len){
	int L,R,p;
	Spilt(root,w,L,R);
	Spilt(R,len,p,R);
	root=Merge(L,R);
}
void Rotate(int len){
	int L,R,p;
	Spilt(root,w,L,R);
	Spilt(R,len,p,R);
	t[p].tag^=1;
	root=Merge(Merge(L,p),R);
}
void Get(){
	int L,R,p;
	Spilt(root,w,L,R);
	Spilt(R,1,p,R);
	cout<<t[p].x;
	if(t[p].x!='\n'&&t[p].x!='\r') cout<<"\n";
	root=Merge(Merge(L,p),R);
}
void Prev(){
	w--;
}
void Next(){
	w++;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	while(n--){
		string op;
		cin>>op;
		if(op=="Move"){
			int k;
			cin>>k;
			Move(k);
		}
		if(op=="Insert"){
			int l;
			cin>>l;
			Insert(l); 
		}
		if(op=="Delete"){
			int l;
			cin>>l;
			Delete(l);
		}
		if(op=="Rotate"){
			int l;
			cin>>l;
			Rotate(l);
		}
		if(op=="Get"){
			Get();
		}
		if(op=="Prev"){
			Prev();
		}
		if(op=="Next"){
			Next();
		}
	} 
	return 0;
}

2025/7/3 10:32
加载中...