//Everyday English:Violet (n.&adj.) 紫罗兰，蓝紫色，紫罗兰色的；堇菜；羞怯的人。 这道题权限题，大意是求区间众数，强制在线。 在XJB出完聚会那道题之后，发现时间复杂度并不好，常数极大，还不支持在线，做完这道题之后才知道自己智障了… 对于输入，先离散化一遍，分成 n \sqrt n n 块。 查询之前，先预处理一下，统计出两个东西： c n t [ i ] [ j ] cnt[i][j] cnt[i][j]和 a n s [ i ] [ j ] ans[i][j] ans[i][j]。 c n t [ i ] [ j ] cnt[i][j] cnt[i][j]表示 i i i这个数在前 j j j块出现的次数； a n s [ i ] [ j ] ans[i][j] ans[i][j]表示从 i i i块到 j j j块的答案，统计的都是整块的答案。 搞定这些的时间复杂度是 O ( n n ) O(n\sqrt n) O(nn )的。 对于 c n t [ i ] [ j ] cnt[i][j] cnt[i][j]的统计，先做出每一块 i i i出现的次数，然后一遍前缀和搞定。对于 a n s [ i ] [ j ] ans[i][j] ans[i][j]的统计，先确定起点 l l l，就是第 i i i块的起点，然后 r r r向后暴力移动统计，当 r r r等于一个块的终点时，记录答案。 对于统计 a n s [ i ] [ j ] ans[i][j] ans[i][j]时，别忘了清数组，看好 r r r… 记完了，有什么用呢？ 对于一次查询，假如左右端点之间一个整块也没有，直接暴力统计即可。如果有整块，就可以利用统计出的答案，先定答案就是之间整块的答案，然后统计零散部分即可。零散部分出现次数可以用之前统计出的前缀和快速求出。 至此，时间复杂度为 O ( ( n + m ) n ) O((n+m)\sqrt n) O((n+m)n )。可解决这个问题，同时也可解决聚会那道题，时间真的加快很多。 必须吐槽题解里的std写的格式太烂了。 Code
