qwq

[Violet]蒲公英

传送门

分块，离散化后维护前 iii 个块中数j的出现次数 sum[i][j]sum[i][j]sum[i][j] 以及块 iii 到块 jjj 的最小众数 p[i][j]p[i][j]p[i][j]，时间复杂度 O(nn)O(n\sqrt n)O(nn​)。

查询区间 [x,y][x,y][x,y] 时，假设 xxx 在第 ststst 个块，yyy 在第 ededed 个块，可能为答案的便只有 [x,rst],[led,y][x,r_{st}],[l_{ed},y][x,rst​],[led​,y] 中的数以及 p[st+1][ed−1]p[st+1][ed-1]p[st+1][ed−1]。暴力扫两个散块，第一次扫到一个数时加上 [st+1,ed−1][st+1,ed-1][st+1,ed−1] 的整块的贡献，维护出现次数最大值及对应的数即可。若没扫到过 p[st+1][ed−1]p[st+1][ed-1]p[st+1][ed−1]，还要再将最大值再与它的出现次数进行比较。

注意桶的动态清空，复杂度不要假掉。

错误思路：

大概是刚学过摩尔投票，上来就有点魔怔。Hack 数据：414524234\ 1\ 4\ 5\ 2\ 4\ 2\ 34 1 4 5 2 4 2 3，查询 [1,4][1,4][1,4]，如果摩尔投票，第一个块的 444 会被屏蔽掉，使得求出来答案为 111 /kk

[SNOI2017]一个简单的询问

传送门

莫队没法一起求两个区间，所以考虑差分，即 q(l1,r1,l2,r2)=q(1,r1,1,r2)−q(1,l1−1,1,r2)−q(1,r1,1,l2−1)+q(1,l1−1,1,l2−1)q(l1,r1,l2,r2)=q(1,r1,1,r2)-q(1,l1-1,1,r2)-q(1,r1,1,l2-1)+q(1,l1-1,1,l2-1)q(l1,r1,l2,r2)=q(1,r1,1,r2)−q(1,l1−1,1,r2)−q(1,r1,1,l2−1)+q(1,l1−1,1,l2−1)，这样就可以用莫队求了，每个询问 q(1,l,1,r)q(1,l,1,r)q(1,l,1,r) 动态维护两个数组记录 [1,l][1,l][1,l] 和 [1,r][1,r][1,r] 中每个数的出现次数就能求出答案。

注意这里和平时求 [l,r][l,r][l,r] 答案的莫队不一样，l←l−1l\gets l-1l←l−1 是删除，l←l+1l\gets l+1l←l+1 是增加。

序列

传送门

欢迎收看 O(nnlog⁡n)O(n\sqrt n\log n)O(nn​logn) 轻松过 1e51e51e5 /fad

发现时间轴 + 位置实际上是二维偏序，可以考虑扫描线，把 [l,r][l,r][l,r] 加 xxx 拆成 [l,n][l,n][l,n] 加 xxx 和 [r+1,n][r+1,n][r+1,n] 减 xxx，将修改和询问都按位置排序，在时间轴上分块，修改即为区间修改 [tim,m][tim,m][tim,m]（mmm 为总操作次数），询问即为询问 [1,tim−1][1,tim-1][1,tim−1]，注意特判 tim=0tim=0tim=0 是否有贡献。

具体地，分块维护每个时间值的变化量，对于每个块内的元素从大到小排序，即可二分求出整块答案。