关于线性基合并
  • 板块学术版
  • 楼主Perfound
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/9/25 18:52
  • 上次更新2023/11/2 18:08:39
查看原帖
关于线性基合并
535259
Perfound楼主2023/9/25 18:52

暴力插入每个线性基中的数的合并的复杂度为什么都说可以在某些条件下均摊啊,我觉得只有下面这种才可以使得每个插入的数最多计算log次才可以在树形合并的条件下均摊。

for(int i=30;~i;i--)if(q[i])
	for(int j=i,x=q[i];~j;j--)if((x>>j)&1)
		{if(p[j])x^=p[j];else{p[j]=x;break;}}
2023/9/25 18:52
加载中...