莫队+分块
EricWan
·
·
题解
一个很典的 trick，我竟然一直不知道，这题让我第一次学到这个 trick。
本题前置知识：分块，莫队，线段树（也许不需要）
简要题意
有一个序列，设 cnt_{l,r,c}=\sum_{i=l}^r[a_i=c]，每次给定 l,r,x，求 \frac{(\sum_{i=1}^{x-1}cnt_{l,r,i})!}{\prod_{i=1}^{x-1}cnt_{l,r,i}!}。
我会暴力（与正解关系不大）
期望得分：0。
## 我会带修莫队（与正解关系不算太大）
通过思考暴力方法，我们发现增加一个元素是好处理的，像这种维护一个桶（也就是我们计算答案用的 $cnt_{l,r}$）的题，我们自然可以想到莫队。
看见这个 $l,r$，看到这个 $x$，看到这个不大的数据范围。
莫队的同时维护一个桶来处理当前的 $cnt_{l,r}$，另外需要维护答案的分母和分子。
带修莫队乎上去，$O(n^\frac53)$ 获得和作者一样的 TLE×15。
期望得分：0。
## 我会莫队加线段树
（我并不会）
观察上面的复杂度（当然不观察暴力直接想到这一步可以），发现把 $x$ 这一维移来移去是一个很慢的操作，我们就考虑不进行带修，用建立在 $x$ 这一维上的线段树维护 $\prod cnt!$ 和 $\sum cnt$，每次查询一个前缀积就可以了。
如果插入一个值为 $i$ 的元素，那么就让线段树维护的 $cnt_{l,r,i}!$ 乘上一个 $cnt_{l,r,i}+1$ 即可，删除同理。
观察复杂度，每次移动一个端点不管是删除还是加入都涉及到线段树单点修改，复杂度是 $O((n+q)\sqrt n\log n)$ 的，移动好之后对于每一个题目的查询需要再线段树上查询前缀积，复杂度是 $O(q\log n)$ 的。
期望得分：0。
## 我会莫队加分块
（我并不会）
还是观察上面的解法的复杂度，我们发现：莫队的**移动**和**查询**的复杂度分配不合理。一个是 $O((n+q)\sqrt n\log n)$，一个是 $O(q\log n)$，差别太大，我们可以考虑再这方面上下手，优化移动复杂度。
这里就是一个用于优化这种东西的典 trick 了，我们使用**分块**而非**线段树**维护，我们把上面的线段树直接替换为分块就好了，在 $x$ 一维上分块，莫队的每次**移动**只会修改一个 $cnt$ 和一个块的 $\prod cnt$ 和 $\sum cnt$，然而**查询**需要访问 $O(\sqrt n)$ 个块的 $\prod cnt!$ 和 $\sum cnt$ 以及一个散块的 $O(\sqrt n)$ 个 $cnt$。通过预处理阶乘和逆元和每个数的逆元等可以做到 $O((n+q)\sqrt n)$。
期望得分：625。
[完整代码链接](https://atcoder.jp/contests/abc405/submissions/65711729)
核心代码：
```cpp
using modulo_int::fixed_modulo::mint; // 我的自动取模机，此题卡常，需稍作更改
#define K 500 // 莫队快长
#define K2 500 // 值域快长
int n, m, a[2000005], ansans[2000005]; // 输入与答案
mint fac[2000005], inv[2000005]; // 预处理，方便将一些 O(log) 优化为 O(1)
int curl, curr, cnt[2000005], sum_cnt[2000005]; // 莫队维护
mint ans, product_cnt_fac[2000005]; // 莫队维护
struct query_struct {
int l, r, x, id;
} q[1000005]; // 查询
void add(int x) { // 莫队扩展
x = a[x];
cnt[x]++;
product_cnt_fac[x / K2] *= cnt[x];
sum_cnt[x / K2]++;
}
void del(int x) { // 莫队收缩
x = a[x];
product_cnt_fac[x / K2] *= inv[cnt[x]];
sum_cnt[x / K2]--;
cnt[x]--;
}
int query_sum(int x) // 查询
{
int ans = 0;
for (int i = 0; i < x / K2; i++) { // 整块
ans += sum_cnt[i];
}
for (int i = x / K2 * K2; i <= x; i++) { // 散块
ans += cnt[i];
}
return ans;
}
mint query_fac_product(int x) { // 查询
mint ans = 1;
for (int i = 0; i < x / K2; i++) { // 整块
ans *= product_cnt_fac[i];
}
for (int i = x / K2 * K2; i <= x; i++) { // 散块
ans *= fac[cnt[i]];
}
return ans;
}
signed main() {
for (int i = 0; i < 2000005; i++) {
product_cnt_fac[i] = 1;
}
MATH::build_factorial<mint, mint>(2000000, fac, nullptr);
for (int i = 1; i <= 2000000; i++) {
inv[i] = mint(1) / mint(i);
} // 上面都是预处理
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r >> q[i].x;
q[i].id = i;
}
sort(q + 1, q + m + 1, [](query_struct a, query_struct b)->bool {
if (a.l / K != b.l / K) {
return a.l / K < b.l / K;
} else if (a.l / K & 1) { // 莫队奇偶优化
return a.r > b.r;
}
return a.r < b.r;
});
curl = 1;
for (int i = 1; i <= m; i++) { // 标准莫队
while (curl > q[i].l) add(--curl);
while (curr < q[i].r) add(++curr);
while (curl < q[i].l) del(curl++);
while (curr > q[i].r) del(curr--);
ansans[q[i].id] = fac[query_sum(q[i].x - 1)] / (query_fac_product(q[i].x - 1) + (mint)mod);
}
for (int i = 1; i <= m; i++)
{
cans << (ansans[i] + mod) % mod << endl;
}
return 0;
}
```