题解 | #战略轰炸#
矩阵交换
https://ac.nowcoder.com/acm/contest/65196/A
更优复杂度。
在题解描述的解法基础上,对根号分治 部分使用值域分块维护而非树状数组可以做到 ,这是因为修改次数只有 次而查询次数有 次。
部分,可以发现查询次数反而只有 ,总修改次数达到 。同样使用值域分块即可做到 。
因此平衡两部分之后复杂度可以做到 。
矩阵交换
https://ac.nowcoder.com/acm/contest/65196/A
更优复杂度。
在题解描述的解法基础上,对根号分治 部分使用值域分块维护而非树状数组可以做到 ,这是因为修改次数只有 次而查询次数有 次。
部分,可以发现查询次数反而只有 ,总修改次数达到 。同样使用值域分块即可做到 。
因此平衡两部分之后复杂度可以做到 。
相关推荐