关于 4041nofoundGeoge 这篇题解的一些问题
查看原帖
关于 4041nofoundGeoge 这篇题解的一些问题
766573
chenbs楼主2024/11/2 17:35

将所有可能的能力值压缩,然后上传是没有什么问题的。但是 mm 次的询问不知道如何解决

我一开始觉得可以离线扫一遍,但是这个节点更新后如何快速判定哪些人可以胜利?


update 简单写了一下(边界可能有点小问题),发现后面不会写了

#define pos(i) ((1<<k)-1+i)
void update(int i, int s) { // i 为人的编号,s 为可能能力值的集合
	int u=pos(i), r=1;
	while((u>>=1) > 1) {
		if(d[u] == 0) { // 左儿子为擂主
			t[u].f |= (t[u<<1].f & (0x3FFFF - ((1<<r)-1)));
			if(t[u<<1].f & ((1<<r)-1)) t[u].f |= t[u<<1|1].f;
		} else { // 右儿子为擂主
			t[u].f |= (t[u<<1|1].f & (0x3FFFF - ((1<<r)-1)));
			if(t[u<<1|1].f & ((1<<r)-1)) t[u].f |= t[u<<1].f;
		}
		++r;
	}
}
2024/11/2 17:35
加载中...