CF700D Huffman Coding on Segment
Codeforces Luogu 分析 考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。 考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\fr...
Codeforces Luogu 分析 考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。 考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\fr...
Luogu 分析 考虑莫队，在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\sqrt{n}\log n)$ 的，由于这是 Ynoi 所以过不了。 由于转移是 $\mathcal{O}(\log n)$ 的，而逆序对数又是个可减的东西，所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的，一个是区间中比 $x$ 小的数的...
Luogu 分析 考虑莫队，并开两个 bitset，分别存 $x$ 是否在区间内和 $100000-x$ 是否在区间内，假设分别叫 $A$ 和 $B$。 那么对于询问 $-$，直接判断 A&(A<<x) 是否有 $1$ 即可；对于询问 $+$，直接判断 B&(A<<(100000-x)) 是否有 $1$ 即可。这两种询问单次都是 $\mathcal{O...
Luogu 分析 考虑每个数的贡献。假设 $x$ 在 $[l,r]$ 中出现了 $c$ 次，则有 $2^{r-l+1}-2^{r-l+1-c}$ 个子序列包含 $x$，所以其贡献为 $x(2^{r-l+1}-2^{r-l+1-c})$。 考虑把出现次数相同的放到一起，即求出每种出现次数对应的数的和。显然可以直接莫队。 注意到出现次数最多只有 $\mathcal{O}(\sqrt{n})$ 种...
Luogu 分析 显然一个询问 $(l_1,r_1,l_2,r_2,l_3,r_3)$ 的答案是 $(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times size$ ，这里的 $size$ 表示三个区间内出现了多少个公共的颜色。 那么只需要考虑如何求 $size$。 首先对所有数离散化，令它离散化后的值为小于等于它的数的个数。 然后当加入一个值 $p$ 的...
Luogu LOJ 分析 这样子就可以把每个询问拆成四个，然后莫队即可。 代码 //It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #includ...