WA 求助
查看原帖
WA 求助
556362
Unnamed114514楼主2023/9/28 23:40
#include<bits/stdc++.h>
#define pii pair<int,int>
#define endl '\n'
using namespace std;
const int N=1e4+5;
int q,root[N],tot;
string s;
mt19937 rnd(0);
struct Treap{ int rk,siz,ls,rs; char key; }t[N<<7];
inline int New(char x){
	t[++tot]=Treap({rnd(),1,0,0,x});
	return tot;
}
inline int clone(int node){
	t[++tot]=t[node];
	return tot;
}
inline void pushup(int rt){ t[rt].siz=t[t[rt].ls].siz+t[t[rt].rs].siz+1; }
int merge(int rt1,int rt2){
	if(!rt1||!rt2) return rt1|rt2;
	if(t[rt1].rk<t[rt2].rk){
		t[rt1].rs=merge(t[rt1].rs,rt2),pushup(rt1);
		return rt1;
	} else{
		t[rt2].ls=merge(rt1,t[rt2].ls),pushup(rt2);
		return rt2;
	}	
}
pii split(int rt,int x){
	if(!rt) return make_pair(0,0);
	pii p;
	rt=clone(rt);
	if(t[t[rt].ls].siz>=x) p=split(t[rt].ls,x),t[rt].ls=p.second,p.second=rt;
	else p=split(t[rt].rs,x-t[t[rt].ls].siz-1),t[rt].rs=p.first,p.first=rt;
	pushup(rt);
	return p;
}
char kth(int rt,int k){
	if(t[t[rt].ls].siz>=k) return kth(t[rt].ls,k);
	if(t[t[rt].ls].siz+1==k) return t[rt].key;
	return kth(t[rt].rs,k-t[t[rt].ls].siz-1);
}
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s>>q;
    for(auto c:s) root[0]=merge(root[0],New(c));
    for(int i=1,op,l,r;i<=q;++i){
    	cin>>op;
    	if(op==1){
    		cin>>l>>r,++l,++r;
    		pii p1=split(root[i-1],l-1),p2=split(p1.second,r-l+1);
    		root[i]=merge(p2.first,merge(p1.first,p2.second));
		} else if(op==2){
			cin>>l>>r,++l,++r;
    		pii p1=split(root[i-1],l-1),p2=split(p1.second,r-l+1);
    		root[i]=merge(merge(p1.first,p2.second),p2.first);
		} else if(op==3){
			cin>>l,++l;
			cout<<kth(root[i-1],l)<<endl;
			root[i]=root[i-1];
		} else if(op==4){
			cin>>l>>r,++r;
			cout<<kth(root[l],r)<<endl;
			root[i]=root[i-1];
		}
	}
	return 0;
}
2023/9/28 23:40
加载中...