一眼看上去感觉是个 fhqTreap 板子，然后写了一个交上去结果 T 飞了，改成线段树之后过掉了

本地测 fhqTreap 不开 O2 要跑 9s 左右，开 O2 跑 6s

求助这个是数据结构自带大常数的缘故吗？还是说我写得太丑了或者写假了？会和 Random 不够优秀有关系吗？

附一个我一开始打的平衡树代码：

#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N=600086,MOD=1e9+7;
int n,m,tot,rt,lc[N],rc[N],pw[N],a[N],sze[N],rnd[N],val[N],sum[N],col[N],cor[N];
int Random(){return rand()<<15|rand();}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
int Add(int &x,int y){return(x+=y)>=MOD?x-=MOD:x;}
int qpow(int a,int b){
	int ret=1;
	while(b){if(b&1)ret=1ll*ret*a%MOD;a=1ll*a*a%MOD;b>>=1;}
	return ret;
}
bool pushup(int k){
	sze[k]=sze[lc[k]]+sze[rc[k]]+1;sum[k]=col[k]=cor[k]=0;
	Add(sum[k],1ll*sum[lc[k]]*pw[sze[rc[k]]+1]%MOD);
	Add(sum[k],1ll*sum[rc[k]]*pw[sze[lc[k]]+1]%MOD);
	Add(sum[k],1ll*col[lc[k]]*cor[rc[k]]%MOD);
	Add(sum[k],1ll*val[k]*col[lc[k]]%MOD*1ll*pw[sze[rc[k]]]%MOD);
	Add(sum[k],1ll*val[k]*cor[rc[k]]%MOD*1ll*pw[sze[lc[k]]]%MOD);
	Add(cor[k],1ll*cor[lc[k]]*pw[sze[rc[k]]+1]%MOD);
	Add(cor[k],1ll*val[k]*pw[sze[rc[k]]]%MOD);
	Add(cor[k],cor[rc[k]]);
	Add(col[k],1ll*col[rc[k]]*pw[sze[lc[k]]+1]%MOD);
	Add(col[k],1ll*val[k]*pw[sze[lc[k]]]%MOD);
	Add(col[k],col[lc[k]]);
	return true;
}
bool split(int np,int k,int &x,int &y){
	if(!np){x=y=0;return true;}
	if(val[np]<=k)x=np,split(rc[np],k,rc[np],y);
	else y=np,split(lc[np],k,x,lc[np]);
	return pushup(np);
}
int Merge(int p,int q){
	if((!p)||(!q))return p|q;
	if(rnd[p]>rnd[q]){rc[p]=Merge(rc[p],q);pushup(p);return p;}
	else{lc[q]=Merge(p,lc[q]);pushup(q);return q;}
}
bool push(int x){
	int tl=0,tr=0;
	val[++tot]=x;sum[tot]=0;col[tot]=cor[tot]=x;rnd[tot]=Random();sze[tot]=1;
	split(rt,x,tl,tr);rt=Merge(Merge(tl,tot),tr);
	return true;
}
bool pop(int x){
	int tl=0,tr=0,tm=0;
	split(rt,x-1,tl,tr);split(tr,x,tm,tr);
	rt=Merge(Merge(tl,Merge(lc[tm],rc[tm])),tr);
	return true;
}
bool debug(int np){
	if(lc[np])debug(lc[np]);
	printf("pos:%d\nrnd=%d\nval=%d\nsum=%d\ncol=%d\ncor=%d\n\n",np,rnd[np],val[np],sum[np],col[np],cor[np]);
	if(rc[np])debug(rc[np]);
	return true;
}
int main(){
	srand((unsigned)time(0));
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	n=read();pw[0]=1;
	for(int i=1;i<=n;i++)push(a[i]=read()),pw[i]=2ll*pw[i-1]%MOD;
	m=read();
	int inv=qpow(pw[n],MOD-2);//debug(rt);
	printf("%d\n",1ll*sum[rt]*inv%MOD);
	for(int i=1;i<=m;i++){
		int x=read();pop(a[x]);push(a[x]=read());//debug(rt);
		printf("%d\n",1ll*sum[rt]*inv%MOD);
	}
	fclose(stdin);fclose(stdout);return 0;
}