violet专题

BZOJ2724 [Violet 6]蒲公英 解题报告【数据结构】【分块】

Description Input 修正一下 l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1 Output Sample Input 6 3 1 2 3 2 1 2 1 5 3 6 1 5 Sample Output 1 2 1 HINT 修正下: n <= 40000, m <=

bzoj2724 [Violet 6]蒲公英 分块

Description 求区间众数,强制在线 Code 一开始yy了一个分块线段树合并的sb做法。。 如果不强制在线的话可以回滚莫队,强制在线考虑分块暴力 先离散。分块中常用的技巧是对块做各种前缀和。本题我们记s[i,j]表示前i块j出现的次数,记r[i,j]为i到j块的答案 对于询问[l,r],我们把在两侧零散出现的数字在中间整块中出现的次数塞进桶里(绕 看图,我们把红色部分出