这4次方的复杂度怎么过的(还是我算错了)
查看原帖
这4次方的复杂度怎么过的(还是我算错了)
683859
complete_binary_tree楼主2024/4/23 20:34

https://www.luogu.com.cn/record/156853116

rt,不想写线段树所以弄了个暴力加边

就是外面 qq 一个循环

while( q-- )

然后复制一份线性基,暴力加边

for( int i = 1; i <= _cnt; ++i ) if( query[i].ishere ) bl2.add( val[query[i].u] ^ val[query[i].v] ^ query[i].w );

线性基是 1000⋅1000ω\displaystyle \frac{1000 \cdot 1000}{\omega} 的,所以总的复杂度上界应该是 1000(q)⋅550(加边)⋅1000⋅1000(线性基)ω\displaystyle \frac{1000(q) \cdot 550(加边) \cdot 1000 \cdot 1000(线性基)}{\omega} 的

取 ω=64\omega = 64 是 8.5e98.5e9,看起来过不了

所以是数据水还是我复杂度算错了呢?

2024/4/23 20:34
加载中...