望月悲叹的最初分块
严格强于区间 rank, 直接考虑分块.
平凡的 \(\mathcal O(n\sqrt{n\log n})\) 做法缺点在于二分这个东西完全用不到分块容易预处理的优秀性质. 本题的值域很小, 二分直接扔掉.
相比较而言, 值域分块和序列分块契合度更高, 考虑值域分块.
设 \(g_{i, j}\) 表示前 \(i\) 块有 \(g_{i, j}\) 个数值为 \(j\), \(G_{i, j}\) 表示前 \(i\) 块有 \(G_{i, j}\) 个数值域在第 \(j\) 块.
查询时先把散块的信息算出来, 然后在值域块上跳, 单次查询块内信息是 \(\mathcal O(1)\) 的, 整体复杂度 \(\mathcal O((n+m)\sqrt n)\).
然后考虑修改. 发现这个修改严格弱于 loj516, 散块暴力重构, 整块打 tag. 整体的复杂度还是 \(\mathcal O((n + m)\sqrt n)\). 代码还没有, 别急.