关于题目 [TJOI2019]甲苯先生的滚榜这题，我的代码无论如何卡不过去最后一个点的10s时限；同学的代码看似好像和我的并没有太大不同 而经过自己造的极限数据测试，单组就可以差出1s以上。

思路都是一样 就是新写了一个类用fhq来维护一下罢了，但是不知道为什么，同学原先过不去的问题是开了五倍空间却RE 开了十倍就过了 而我的问题是为什么好像很像的代码常数差距如此之大

能麻烦大佬指出一下常数巨大的原因吗/dk 十分感谢！

同学代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std ;
typedef unsigned int ui ;

struct Node
{
	ui ria , rib ;
	friend bool operator < ( Node u , Node v )
	{
		if ( u .ria == v .ria )
			return u .rib < v .rib ;
		return u .ria > v .ria ;
	}
} v[2000005] ;

ui m , n , seed , root , cnt , ra , rb , last = 7 ;
ui t[2000005][2] , c[2000005] , s[2000005] ;

inline int read()
{
	int re=0,k=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
	return re*k;
}

inline void write(int x)//这个必须要，不然会t得很惨
{
	if(x<10)
	{
		putchar(x+48);
		return;
	}
	write(x/10),write(x%10);
}

ui randoom ( )
{
	return rand ( ) << 5 & rand ( ) | rand ( ) ;
}

Node made ( ui ia , ui ib )
{
	Node vmd ;
	vmd .ria = ia ;
	vmd .rib = ib ;
	return vmd ;
}

ui newnode ( Node x )
{
	c [ ++ cnt ] = randoom ( ) ;
	s [ cnt ] = 1 ;
	v [ cnt ] = x ;
	t [ cnt ] [ 0 ] = t [ cnt ] [ 1 ] = 0 ;
	return cnt ;
}

void update ( ui now )
{
	s [ now ] = s [ t [ now ] [ 0 ] ] + s [ t [ now ] [ 1 ] ] + 1 ;
}

//void dfs ( ui now )
//{
//	if ( !now )
//		return ;
//	dfs ( t [ now ] [ 0 ] ) ;
//	cout << now << " : " << v [ now ] .ria << " , " << v [ now ] .rib << endl ;
//	dfs ( t [ now ] [ 1 ] ) ;
//}

void split ( ui now , Node k , ui &x , ui &y )
{
	if ( !now ) { x = y = 0 ; return ; }
	if ( v [ now ] < k )
		x = now , split ( t [ now ] [ 1 ] , k , t [ now ] [ 1 ] , y ) ;
	else
		y = now , split ( t [ now ] [ 0 ] , k , x , t [ now ] [ 0 ] ) ;
	update ( now ) ;
}

ui merge ( ui x , ui y )
{
//	cout << "merge : " << x << "  " << y << endl ;
	if ( !x || !y )
		return x + y ;
	if ( c [ x ] < c [ y ] )
	{
//		cout << "first : " << t [ x ] [ 1 ] << "  " << y << endl ;
		t [ x ] [ 1 ] = merge ( t [ x ] [ 1 ] , y ) ;
//		cout << "then : " << t [ x ] [ 1 ] << "  " << y << endl ;
		update ( x ) ;
		return x ;
	}
	else
	{
		t [ y ] [ 0 ] = merge ( x , t [ y ] [ 0 ] ) ;
		update ( y ) ;
		return y ;
	}
}

ui randNum ( ui &seed , ui last , const ui m )
{
    seed = seed * 17 + last ;
	return seed % m + 1 ;
}

ui a , b , d , e ;

void dele ( Node x )
{
	Node y = x ;
	
//		cout << "X : " << x .ria << " : " << y .rib << endl ;
	
	split ( root , x , a , b ) ;
	
//		cout << "root : " << endl ;
//		dfs ( root ) ;
//		cout << endl ;
//	
//		cout << " b : " << endl ;
//		dfs ( b ) ;
//		cout << endl ;
	
	++ y .rib ;
	
	split ( b , y , b , d ) ;
	
//		cout << " b : " << endl ;
//		dfs ( b ) ;
//		cout << endl ;
//	
//	
//		cout << " d : " << endl ;
//		dfs ( d ) ;
//		cout << endl ;
	
	b = merge ( t [ b ] [ 0 ] , t [ b ] [ 1 ] ) ;
	
//		cout << " b : " << endl ;
//		dfs ( b ) ;
//		cout << endl ;
	
	root = merge ( merge ( a , b ) , d ) ;
	
//		cout << "root : " << endl ;
//		dfs ( root ) ;
//		cout << endl ;
}

void init ( )
{
	for ( int i = 1 ; i <= cnt ; ++ i )
	{
		v [ i ] .ria = v [ i ] .rib = 0 ;
		t [ i ] [ 1 ] = t [ i ] [ 0 ] = 0 ;
		s [ i ] = 0 ;
	}
	root = cnt = 0 ;
}

int main ( )
{
//	srand ( time ( NULL ) ) ;
	int T ;
	T = read ( ) ;
//	cin >> T ;
	while ( T -- )
	{
		m = read ( ) ;
		n = read ( ) ;
		seed = read ( ) ;
//		cin >> m >> n >> seed ;
		init ( ) ;
		for ( int i = 1 ; i <= m ; ++ i )
			newnode ( made ( 0 , 0 ) ) ;
		for ( int i = 1 ; i <= m ; ++ i )
			root = merge ( root , newnode ( made ( 0 , 0 ) ) ) ;
		for ( int i = 1 ; i <= n ; ++ i )
		{
			ra = randNum ( seed , last , m ) ;
			rb = randNum ( seed , last , m ) ;
//			cout << " N : " << i << " :  " << ra << " , " << rb << endl ;
			
//			cout << endl << "Delete : " << endl ;
			dele ( v [ ra ] ) ;
//			cout << endl ;
//			cout << "dfs : rot " << endl ;
//			dfs ( root ) ;
//			cout << endl ;
			++ v [ ra ] .ria ;
			v [ ra ] .rib += rb ;
			split ( root , v [ ra ] , a , b ) ;
			
			last = s [ a ] ;
			write ( last ) ;
			putchar ('\n') ;
//			cout << last << endl ;
			
//			cout << "dfs : a " ;
//			dfs ( a ) ;
//			cout << endl ;
//			cout << "dfs : b " ;
//			dfs ( b ) ;
//			cout << endl ;
			
			root = merge ( a , newnode ( v [ ra ] ) ) ;
//			cout << "dfs : root " << endl ;
//			dfs ( root ) ;
//			cout << endl ;
			root = merge ( root , b ) ;
//			cout << "dfs : root " << endl ;
//			dfs ( root ) ;
//			cout << endl ;
		}
	}
	return 0 ;
}

我的代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0;
   char ch=getchar();
   while(!isdigit(ch))ch=getchar();
   while(isdigit(ch)){
   	s=s*10-48+ch;
   	ch=getchar();
   }
   return s;
}
struct V{
   int ria,rib;
   bool operator<(const V&B)const{
   	if(ria==B.ria)return rib<B.rib;
   	return ria>B.ria;
   }
   bool operator<=(const V&B)const{
   	if(ria==B.ria)return rib<=B.rib;
   	return ria>=B.ria;
   }
};
const int MAXN=1e5+10;
int tr[MAXN<<1][2],siz[MAXN<<1],cnt,cv[MAXN<<1],pa[MAXN<<1],rt;
int rub[MAXN<<1],top; 
V val[MAXN],a[MAXN];
inline void pushup(int x){
   siz[x]=siz[tr[x][0]]+siz[tr[x][1]]+1;
   pa[tr[x][0]]=pa[tr[x][1]]=x;
}
inline int rd(){return rand()<<15|rand();}
int build(V v){
   int newnode;
   if(top)newnode=rub[top--];
   else newnode=++cnt;
   val[newnode]=v;
   siz[newnode]=1;
   cv[newnode]=rd();
   tr[newnode][0]=tr[newnode][1]=0;
   return newnode;
}
void split(int now,V k,int &x,int &y){
   if(!now){x=y=0;return;}
   if(val[now]<=k)x=now,split(tr[now][1],k,tr[now][1],y);
   else y=now,split(tr[now][0],k,x,tr[now][0]);
   pushup(now);
}
int merge(int x,int y){
   if(!x||!y)return x+y;
   if(cv[x]<cv[y]){
   	tr[x][1]=merge(tr[x][1],y);
   	pushup(x);return x;
   }
   else {
   	tr[y][0]=merge(x,tr[y][0]);
   	pushup(y);return y;
   }
}
typedef unsigned int ui ;
ui last=7,seed;
ui randNum( ui& seed , ui last , const ui m){ 
   seed = seed * 17 + last ; return seed % m + 1; 
}
int getpos(int x){
   int res=siz[tr[x][0]]+1;
   while(pa[x]){
   	if(x==tr[pa[x]][1]){
   		res+=1+siz[tr[pa[x]][0]];
   	}
   	x=pa[x];
   }
   return res;
}
inline void write(int x){
   if(x<0)putchar('-');
   if(x>9)write(x/10);
   putchar(x%10+48);
}
void ins(V v){
   int x,y;
   split(rt,v,x,y);
   rt=merge(merge(x,build(v)),y);
}
void del(V v){
   int x,y,z;
   split(rt,v,x,y);
   V vv=v;vv.rib--;
   split(x,vv,x,z);
   int f=z;
   z=merge(tr[z][0],tr[z][1]);
   rt=merge(merge(x,z),y);
   
   rub[++top]=f;
   tr[f][0]=tr[f][1]=cv[f]=siz[f]=0;
   val[f]=(V){0,0};
   
}
void ask(V v){
   int x,y;
   V vv=v;vv.rib--;
   split(rt,vv,x,y);
   last=siz[x];
   write(last);puts("");
   rt=merge(x,y);
   return;
}
int T,m,n;
int main(){
   T=read();
   for(;T;T--){
   	srand(20060727);
   	rt=cnt=top=0; 
   	m=read(),n=read();seed=read();
   	for(register int i=1;i<=m;++i)a[i]=(V){0,0},ins(a[i]);
   	for(register int i=1;i<=n;++i){
   		register int u=randNum(seed,last,m);
   		register int v=randNum(seed,last,m);
   		del(a[u]);
   		a[u].ria++;
   		a[u].rib+=v;
   		ins(a[u]);
   		ask(a[u]);
   	}
   }
   return 0;
}
/*
4 3
7 5
7 6
*/

对着同学的乱改后的我的代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std ;
inline int read()
{
	int re=0,k=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
	return re*k;
}

inline void write(int x)//这个必须要，不然会t得很惨
{
	if(x<10)
	{
		putchar(x+48);
		return;
	}
	write(x/10),write(x%10);
}
struct V{
	int ria,rib;
	bool operator<=(const V&B)const{
		if(ria==B.ria)return rib<=B.rib;
		return ria>=B.ria;
	}
};
V made ( int ia , int ib )
{
	V vmd ;
	vmd .ria = ia ;
	vmd .rib = ib ;
	return vmd ;
}

const int MAXN=3e6+10;
int tr[MAXN<<1][2],siz[MAXN<<1],cnt,cv[MAXN<<1],pa[MAXN<<1],rt;
V val[MAXN],a[MAXN];
inline void pushup(int x){
	siz[x]=siz[tr[x][0]]+siz[tr[x][1]]+1;
	pa[tr[x][0]]=pa[tr[x][1]]=x;
}
inline int rd(){return rand()<<15|rand();}
inline int build(V v){
	int newnode=++cnt;
	val[newnode]=v;
	siz[newnode]=1;
	cv[newnode]=rd();
	tr[newnode][0]=tr[newnode][1]=0;
	return newnode;
}
void split(int now,V k,int &x,int &y){
	if(!now){x=y=0;return;}
	if(val[now]<=k)x=now,split(tr[now][1],k,tr[now][1],y);
	else y=now,split(tr[now][0],k,x,tr[now][0]);
	pushup(now);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(cv[x]<cv[y]){
		tr[x][1]=merge(tr[x][1],y);
		pushup(x);return x;
	}
	else {
		tr[y][0]=merge(x,tr[y][0]);
		pushup(y);return y;
	}
}
typedef unsigned int ui ;
ui last=7,seed;
ui randNum( ui& seed , ui last , const ui m){ 
    seed = seed * 17 + last ; return seed % m + 1; 
}
inline void ins(V v){
	int x,y;
	split(rt,v,x,y);
	rt=merge(merge(x,build(v)),y);
}
inline void del(V v){
	int x,y,z;
	split(rt,v,x,y);
	V vv=v;vv.rib--;
	split(x,vv,x,z);
	z=merge(tr[z][0],tr[z][1]);
	rt=merge(merge(x,z),y);
}
inline void ask(V v){
	int x,y;
	V vv=v;vv.rib--;
	split(rt,vv,x,y);
	last=siz[x];
	write(last);puts("");
	rt=merge(x,y);
	return;
}
int T,m,n;
int main(){
	T=read();
	for(;T;T--){
//		srand(20060727);
		rt=cnt=0; 
		m=read(),n=read();seed=read();
		for(int i=1;i<=m;++i)a[i]=made ( 0 , 0 ) , ins(a[i]);
		for(int i=1;i<=n;++i){
			int u=randNum(seed,last,m);
			int v=randNum(seed,last,m);
			del(a[u]);
			a[u].ria++;
			a[u].rib+=v;
			ins(a[u]);
			ask(a[u]);
		}
	}
	return 0;
}
/*
4 3
7 5
7 6
*/