题解：ABC405G [莫队] [分块] [平衡复杂度]

· · 题解

DS 好题。

思路

看到 n,q \le 2.5\times 10^5，区间查询，没有修改，支持离线，自然想到莫队。

简单分析一下题面里的问题，组合数推式子可得答案为 \frac{s}{\prod a_i}，其中 s 为元素个数，a_i 为同样的元素出现次数。

最原始的想法就是维护一下前缀的 s, \prod a_i^{-1} 的信息。可以通过预处理阶乘和逆元，使用 BIT。总时间复杂度是 O(n\sqrt q\log n)，无法通过。

观察一下，修改总复杂度是 O(n\sqrt q\log n)，查询总复杂度是 O(q\log n)，瓶颈在修改。所以我们可以把 BIT 换成值域分块，目的是平衡复杂度，单次修改 O(1)，单次查询 O(\sqrt n)，总时间复杂度 O(n\sqrt q)，可以通过。我跑了 1800ms，这题轻微卡常。

代码

注释部分是 BIT 的写法，可以参考。

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define fi first
#define se second
#define y1 noip200
#define stp(x) fixed << setprecision(x)

using namespace std;

const int N = 3e5 + 50, p = 998244353, inf = 1 << 29;

int n, q, B1, B2, a[N], col[N];
int cnt[N], sum[N], Cnt[N], Sum[N], ans[N];
int mul[N], inv[N];

struct node {
    int l, r, x, id;
    node() {}
    node(int L, int R) {l = L, r = R;}
} b[N];
bool operator < (const node &x, const node &y) {
    if (x.l / B1 == y.l / B1) return x.r < y.r;
    else return x.l / B1 < y.l / B1;
}

void init() {

}

int query(int x) {
    // int res1 = 0, res2 = 1;
    // for (int i = x; i; i -= i & -i) 
        // res1 += cnt[i];
    // for (int i = x; i; i -= i & -i) 
        // res2 = 1LL * res2 * sum[i] % p;
    // return 1LL * mul[res1] * res2 % p;
    --x;
    int y = 0, res1 = 0, res2 = 1;
    while ((y + 1) * B2 <= x) res1 += Cnt[y], res2 = 1LL * res2 * Sum[y] % p, ++y;
    y *= B2;
    while (y <= x) {
        res1 += cnt[y], res2 = 1LL * res2 * sum[y] % p;
        ++y;
    }
    return 1LL * mul[res1] * res2 % p;
}

void add(int x) {
    // x = a[x];
    // col[x]++;
    // for (int i = x; i <= n; i += i & -i) cnt[i]++;
    // for (int i = x; i <= n; i += i & -i) sum[i] = 1LL * sum[i] * inv[col[x]] % p;
    x = a[x] - 1;
    col[x]++;
    cnt[x]++;
    Cnt[x / B2]++;
    sum[x] = 1LL * sum[x] * inv[col[x]] % p;
    Sum[x / B2] = 1LL * Sum[x / B2] * inv[col[x]] % p;
}

void del(int x) {
    // x = a[x];
    // for (int i = x; i <= n; i += i & -i) cnt[i]--;
    // for (int i = x; i <= n; i += i & -i) sum[i] = 1LL * sum[i] * col[x] % p;
    // col[x]--;
    x = a[x] - 1;
    cnt[x]--;
    Cnt[x / B2]--;
    sum[x] = 1LL * sum[x] * col[x] % p;
    Sum[x / B2] = 1LL * Sum[x / B2] * col[x] % p;
    col[x]--;
}

void solve() {
    cin >> n >> q;
    mul[0] = 1;
    for (int i = 1; i <= n; i++) mul[i] = 1LL * mul[i - 1] * i % p;
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = 1LL * (p - p / i) * inv[p % i] % p;
    B1 = n / sqrt(q);
    B2 = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= q; i++) cin >> b[i].l >> b[i].r >> b[i].x, b[i].id = i;
    sort(b + 1, b + q + 1);
    int l = 1, r = 0;
    for (int i = 0; i < n; i++) cnt[i] = Cnt[i] = 0, sum[i] = Sum[i] = 1;
    for (int i = 1; i <= q; i++) {
        while (l > b[i].l) add(--l);
        while (r < b[i].r) add(++r);
        while (l < b[i].l) del(l++);
        while (r > b[i].r) del(r--);
        ans[b[i].id] = query(b[i].x - 1);
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}