模拟赛时,使用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的常数(空间与时间)到底多大