题解：AT_abc421_f [ABC421F] Erase between X and Y

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

int q;
int nxt[5*114514],lst[5*114514];

int place[5*114514];	//代表不删除序列的元素顺序！ 

int op[5*114514];
int x[5*114514],y[5*114514],z[5*114514];
signed main(){
	cin>>q;
	nxt[0]=q+1,lst[q+1]=0;	//代表节点  
	for(int i=1;i<=q;i++){
		cin>>op[i];
		if(op[i]==1){
			cin>>x[i];
			int lst1=x[i],nxt1=nxt[x[i]];	//代表未来节点的位置 
			nxt[lst1]=i,lst[i]=lst1;
			lst[nxt1]=i,nxt[i]=nxt1;	//代表现在的位置  
		}
		else{
			cin>>y[i]>>z[i]; 
		} 
        int now=0;
        // cout<<'!';
        // while(now!=q+1){
        //     cout<<now<<' ';
        //     now=nxt[now];
        // }
        // cout<<endl;
	}
	int now=0;
	place[now]=1;
	int ptr=1;
	while(now!=q+1){
		now=nxt[now];
		ptr++;
		place[now]=ptr;
		// cout<<now<<' ';
	}
 //    for(int i=0;i<=q;i++){
 //        cout<<'#'<<i<<' '<<place[i]<<endl;
 //    }
	// cout<<endl;
	for(int i=0;i<=q;i++){
		nxt[i]=lst[i]=0;	//更新位置！ 离线做法的精髓！  
	} 
	nxt[0]=q+1,lst[q+1]=0;
	for(int i=1;i<=q;i++){
		if(op[i]==1){
			int lst1=x[i],nxt1=nxt[x[i]];	//代表未来节点的位置 
			nxt[lst1]=i,lst[i]=lst1;
			lst[nxt1]=i,nxt[i]=nxt1;	//代表现在的位置  
		}
		else{
			int st=y[i],ed=z[i];
            // cout<<st<<' '<<ed<<endl;
            // cout<<place[st]<<' '<<place
			if(place[st]>place[ed])	swap(st,ed);	//精髓！
			int now=nxt[st];
			int include13=0;
            // cout<<st<<' '<<ed<<endl;
			while(now!=ed){
				int nxt1=nxt[now],lst1=lst[now];
				nxt[lst1]=nxt1,lst[nxt1]=lst1;
				include13+=now;
				nxt[now]=lst[now]=0; 
				now=nxt1;	//代表目前的情况  
			} 
			cout<<include13<<endl;
		} 
		int now=0;
		// cout<<"不朽！"<<' ';
		// while(now!=q+1){
		// 	cout<<now<<' ';
		// 	now=nxt[now];
		// } 
		// cout<<endl;
	} 
	cout<<endl;
	return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！