关于gp hash table
  • 板块学术版
  • 楼主ReqCxmChtChr
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/14 12:06
  • 上次更新2024/7/14 14:04:43
查看原帖
关于gp hash table
421451
ReqCxmChtChr楼主2024/7/14 12:06

模拟赛时,使用gp_hash_table来动态开点开多个树状数组。如下:

gp_hash_table<short,int>Su[MAXN*MAXN];
void add(int x,int v,int c){while(x<=m){Su[c][x]=(Su[c][x]+v)%MOD;x+=lowbit(x);}}
int que(int x,int c){int rs=0;while(x){rs=(rs+Su[c][x])%MOD;x-=lowbit(x);}return rs;}

其中MAXN=750,m<=750,MLE,限制128MB

若把树状数组编号与访问下标调换

gp_hash_table<int,int>Su[MAXN];
void add(int x,int v,int c){while(x<=m){Su[x][c]=(Su[x][c]+v)%MOD;x+=lowbit(x);}}
int que(int x,int c){int rs=0;while(x){rs=(rs+Su[x][c])%MOD;x-=lowbit(x);}return rs;}

则发生TLE(但是多了一个点没有MLE)

最离谱的是,动态开点线段树是正解.

求助,gp_hash_table的常数(空间与时间)到底多大

2024/7/14 12:06
加载中...