Java教程

【草稿】Ynoi 2006 rmpq

本文主要是介绍【草稿】Ynoi 2006 rmpq，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Data 是没有交换律的，意味着所有的操作都要按时间来。

如果平面上横着竖着加起来有 \(n\) 条直线，那么最多将平面划分的区域数是 \(n^2\) 级别的。不妨考虑操作分块，每 \(B\) 个修改分一个块，在一个块内维护每个区域的标记。接下来讨论一些细节：

  • 建立标记结构：一行块一行块的考虑，时间复杂度是 \(O(B^2)\)，操作次数是 \(O(B^2)\) 的，常数小。
  • 找到所属区域：找到其前面有多少竖线，上面有多少横线即可，这个可以用二分完成。
  • 散块查询信息：暴力考虑所有的询问，操作次数是 \(O(\frac{n}{B})\) 的。

仔细算一下操作次数，感觉会被卡。

不妨考虑用二进制分组的方式处理散块。

明天细想先睡觉了。

这篇关于【草稿】Ynoi 2006 rmpq的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航