Yuno

题意 给定序列 \(s\)，每次询问 \(l, r\) 的区间众数的出现次数。 强制在线。空间：\(62.5MB\)。 Sol 蒲公英卡常卡空间版。 考虑优化那个 \(n \times m\) 的数组。 我们要求 \(l, r\) 之中某个数的个数。 乍一看不好弄，仔细想想就会发现，如果我们知道当前 ......

Description 给你一个长为 \(n\) 的排列，\(m\) 次询问，每次查询一个区间的逆序对数，强制在线。 link \(1\leq n,m\leq 10^5\)。 Solution 考虑分块。 首先如果 \(l,r\) 在同一个块内，可以对于每个块暴力二维前缀和预处理。 如果 \(l,r ......

# Yuno loves sqrt technology III ## 题意 区间询问众数，强制在线。 ## 题解 经典分块题，记一下。 对于序列分块，记 $f_{i,j}$ 代表第 $i$ 个块到第 $j$ 个块的众数出现次数。 考虑询问的时候怎么做，我们只需要考虑散块。 对于散块的元素 $a_i ......

[题目 Link](https://www.luogu.com.cn/problem/P5046) 分块，首先预处理所有整块之间的答案，这部分用类似莫队二离的手法可以改成 $O(n)$ 次插入和 $O(n\sqrt{n})$ 查询，然后根号平衡一手做到 $O(n\sqrt{n})$；空间自然也是能线 ......