HELP!!!

fhq_treap

最高一次得了90,交了几十遍,答案更随机值有关。

#include<bits/stdc++.h>
#define N 100100
#define LL long long
#define Un unsigned
using namespace std;
const Un LL k=1517;
int n;
Un LL s[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
char s1[N];
Un LL _hash[N],fk[N],v[N],key[N],size[N];
int ls[N],rs[N],RT,cnt;
struct Tree
{
	void init()
	{
		fk[0]=1;
		for(int i=1;i<=n+1;++i)fk[i]=fk[i-1]*k;
	}
	void pushup(int i)
	{
		_hash[i]=_hash[rs[i]]+fk[size[rs[i]]]*v[i]+fk[size[rs[i]]+1]*_hash[ls[i]];
		size[i]=size[ls[i]]+size[rs[i]]+1;
	}
	int merge(int x,int y)
	{
		if(!x||!y)return x+y;
		int now;
		if(key[x]<key[y])
		{
			now=x;
			rs[x]=merge(rs[x],y);
		}
		else
		{
			now=y;
			ls[y]=merge(x,ls[y]); 
		}
		pushup(now);
		return now;
	}
	void split_rank(int now,int k,int &x,int &y)
	{
		if(!now)
		{
			x=y=0;
			return ;
		}
		if(size[ls[now]]>=k)
		{
			y=now;
			split_rank(ls[now],k,x,ls[y]);
		}
		else
		{
			x=now;
			split_rank(rs[now],k-size[ls[now]]-1,rs[now],y);
		}
		pushup(now);
	}
	int build(int l,int r,int fa)
	{
		if(l>r)return 0;
		int pos=++cnt;
		int mid=(l+r)>>1;
		_hash[pos]=s[mid];
		v[pos]=s[mid];
		size[pos]=1;
		key[pos]=key[fa]+rand();
		ls[pos]=build(l,mid-1,pos);
		rs[pos]=build(mid+1,r,pos);
		pushup(pos);
        return pos;
	}
	void Build(int l,int r)
	{
		RT=build(l,r,0);
	}
	void update(int pos,Un LL ch)
	{
		int a,b,c,d;
		split_rank(RT,pos-1,a,b);
		split_rank(b,1,c,d);
		_hash[c]=v[c]=ch;
		RT=merge(a,merge(c,d));
	}
	void add(int pos,Un LL x)
	{
		int a,b;
		split_rank(RT,pos,a,b);
		++cnt;
		_hash[cnt]=x;
		v[cnt]=x;
		size[cnt]=1;key[cnt]=rand();
		RT=merge(merge(a,cnt),b);
	}
	LL get_(int l,int len)
	{
		int a,b,c,d;
		Un LL res=0;
		split_rank(RT,l-1,a,b);
		split_rank(b,len,c,d);
		res=_hash[c];
		RT=merge(a,merge(c,d));
		return res;
	}
	void query(int x,int y)
	{
		int l=1,r=min(n-x+1,n-y+1),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get_(x,mid)==get_(y,mid))res=mid,l=mid+1;
			else r=mid-1;
		}
		printf("%d\n",res);
	}
}T;
int main()
{
    srand(time(0));
	scanf("%s",s1+1);
	n=strlen(s1+1);
	T.init();
	for(int i=1;i<=n;++i)s[i]=(Un LL)(s1[i]-'a');
	T.Build(1,n);
	int m=read(),x;
	char opt[10],ch[10];
	while(m--)
	{
		scanf("%s",opt);
		if(opt[0]=='Q')
		{
			x=read();
			int y=read();
			T.query(x,y);
		}
		else if(opt[0]=='R')
		{
			x=read();scanf("%s",ch);
			Un LL y=(Un LL)(ch[0]-'a');
			T.update(x,y);
		}
		else
		{
			++n;
			x=read();scanf("%s",ch);
			Un LL y=(Un LL)(ch[0]-'a');
			T.add(x,y);
		}
	}
	return 0;
}

舅舅我啊