P4008求助
  • 板块灌水区
  • 楼主lfxxx_
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/10/25 16:34
  • 上次更新2024/10/25 18:17:10
查看原帖
P4008求助
795344
lfxxx_楼主2024/10/25 16:34
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+5;
mt19937 rng(time(0));
int root,tot;
struct node{
    int val,pri,ls,rs,sz;
}tr[N];
int New(int x)
{
    ++tot;
    tr[tot].val=x;
    tr[tot].pri=rng();
    tr[tot].sz=1;
    return tot;
}
void pushup(int p){tr[p].sz=tr[tr[p].ls].sz+tr[tr[p].rs].sz+1;}
void split(int p,int k,int &L,int &R)
{
    if(!p)
    {
        L=R=0;
        return;
    }
    if(tr[tr[p].ls].sz<k)
    {
        L=p;
        split(tr[p].rs,k-tr[tr[p].ls].sz-1,tr[p].rs,R);
    }
    else
    {
        R=p;
        split(tr[p].ls,k,L,tr[p].ls);
    }
    pushup(p);
}
int merge(int L,int R)
{
    if(!L||!R)
        return L+R;
    if(tr[L].pri<=tr[R].pri)
    {
        tr[L].rs=merge(tr[L].rs,R);
        pushup(L);
        return L;
    }
    tr[R].ls=merge(L,tr[R].ls);
    pushup(R);
    return R;
}
void print(int rt)
{
	if(!rt)
		return ;
	print(tr[rt].ls);
	cout<<(char)(tr[rt].val); 
	print(tr[rt].rs);
}
signed main()
{
//	freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m,pos=0;
    cin>>m;
    while(m--)
    {
    	string op;
    	cin>>op;
    	if(op=="Move")
    	{
    		int x;
    		cin>>x;
    		pos=x;
		}
		if(op=="Insert")
		{
			int n,L,R;
			cin>>n;
			split(root,pos,L,R);
			for(int i=1;i<=n;++i)
			{
				char ch=getchar();
				while(ch=='\n')
					ch=getchar();
				L=merge(L,New(ch));
			}
			root=merge(L,R);
		}
		if(op=="Delete")
		{
			int n,L,R,p;
			cin>>n;
			split(root,pos,L,R);
			split(R,n,R,p);
			root=merge(L,p); 
		}
		if(op=="Get")
		{
			int n,L,R,p;
			cin>>n;
			split(root,pos,L,R);
			split(R,n,R,p);
			print(R);
			cout<<'\n';
			root=merge(L,merge(R,p));
		}
		if(op=="Prev")
			--pos;
		if(op=="Next")
			++pos;
	}
}

0pts 阳历过了

2024/10/25 16:34
加载中...