mxqz
  • 板块学术版
  • 楼主wzc_IOI_czl
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/8 15:33
  • 上次更新2023/11/3 11:02:56
查看原帖
mxqz
539724
wzc_IOI_czl楼主2023/7/8 15:33

给定 n,你需要维护三维空间中三个维度坐标都在 1~n 的整点(共 n3n^3 个)
每次操作要么一个点向他的六相邻点中的一个(若 (x1−x2)2+(y1−y2)2+(z1−z2)2=1(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2=1,则 (x1,y1,z1)(x_1,y_1,z_1) 和 (x2,y2,z2)(x_2,y_2,z_2) 六相邻)连/断边(即改变连边状态)
要么查询一个点所在连通块的x y z 坐标最大最小值
qq 为操作次数,期望复杂度 O(n3+qn2)O(n^3+qn^2)

2023/7/8 15:33
加载中...