现在才想起来之前忘水了

提醒：最后1个点是毒瘤数据
input:
1 1
0 1 1 100
WA output:
100
AC output:
100
0

比赛时连分块都要调试半天的我实在是太蒻了，说实话当时要不是一位神犇问我能不能用分块我还真没想起来能用分块

这里是为了可以用可持久化线段树混过去而故意开大内存的屑林荫
内存已改回

调试了半天是自增的问题，以后再也不把自增表达式写在语句里面了。。。

回复 @Skylake :
这种类型的题目也许来自于神中神陈立杰（orz%%%）的文章《区间众数解题报告》，在文章中，WJMZBMR神犇提到了除了$O((n + q) \sqrt n \log n)$ 的二分查找的做法之外的优化做法，实现了 $O((n + q) \sqrt n)$ 的时间复杂度（当然这一题不强制在线，神犇的莫队解法也很优秀，对于空间的要求要更小，比如这一题我用这个方法就会超内存），文章甚至提到了带修的区间众数解法，很具参考意义，可以看一下，已上传至 Onedrive

参考clj大佬论文《区间众数命题报告》，预处理每个块中数的数量，相比《进阶指南》的二分做法效率显著提高（具体来说，同开O2的情况下快了将近1s），时间复杂度从$O((n + m) \sqrt n \log n)$ 优化至 $O((n + m) \sqrt n)$。唯一的缺点就是代码难度剧增（调试起来很痛苦，比如我数组大小是按照 $O(n^{1.5})$ 来的，但是分块大小还是选择的 $O(\sqrt{n \log n})$，导致调试了一下午发现不了问题，包括边界问题也调整了半天）。至于WJMZBMR神犇的论文可以参考这里 Onedrive，很有参考价值

学习莫队算法

回复 @FoolMike :
蒲公英 这个题是《算法竞赛进阶指南》上的例题，从 BZOJ 搬过来的，重题只能说是个巧合叭。
不过本题的做法我找了一圈没找到，应该（大概）不会重题。。的吧

回复 @Skylake :
原题和这个题重复了数字查询

标程已提交，没有经过他人验题，如果有误请联系我

很像廊桥分配

1

注意两个牛交集不可以被分到一个畜栏

记得开longlong

读入数据都要n的时间

数据已修改

第一个dijkatra

，

不带文件输入输出，洛谷可以AC，带文件输入输出就RE