关于题目 [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
*/