题解：AT_abc405_g [ABC405G] Range Shuffle Query

· · 题解

对于一个区间，数字 i 出现次数为 c_i，则答案为 \dfrac{(\sum_{i=1}^{x-1}c_i)!}{\prod_{i=1}^{x-1}(c_i!)}，这部分很典了，就是全排列除掉相同数字之间的顺序。

考虑用莫队移动，树状数组维护 c 数组前缀和、前缀积，时间复杂度 O(n\sqrt q\log n+q\log n)，直接被卡飞。把树状数组换成 O(1)-O(\sqrt n) 的值域分块就行了（莫队套值域分块也很典了），时间复杂度 O(n\sqrt q+q\sqrt n)。注意能预处理的尽量预处理了（比如阶乘和逆元）。还有要注意一点，把莫队的加操作放在减操作之前，不然会访问负数的逆元就爆了。

综上是道典题。代码超级好写。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2.5e5+7;
const int mod=998244353;
int B=501;
int n,q;
int a[maxn],inv[maxn];
struct node{
    int l,r,x,id;
    bool operator<(const node &o)const{
        if(l/B==o.l/B) return r<o.r;
        return l<o.l;
    }
}b[maxn];
#define bl(x) (((x)-1)/B+1)
#define st(x) ((bl(x)-1)*B+1)
#define ed(x) (bl(x)*B)
int ton[maxn],ans[maxn],fac[maxn];
int pre[maxn],prv[maxn],mum[maxn];
void add(int x){
    pre[bl(a[x])]++;
    ton[a[x]]++; 
    prv[bl(a[x])]=prv[bl(a[x])]*ton[a[x]]%mod;
    mum[a[x]]=mum[a[x]]*ton[a[x]]%mod;
}
void del(int x){
    pre[bl(a[x])]--;
    ton[a[x]]--; 
    prv[bl(a[x])]=prv[bl(a[x])]*inv[ton[a[x]]+1]%mod;
    mum[a[x]]=mum[a[x]]*inv[ton[a[x]]+1]%mod;
}
int qpow(int a,int b){
    int res=1;
    for(;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q; B=n/sqrt(q);
    inv[1]=1;
    for(int i=2;i<=n+2;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    fac[0]=1;
    for(int i=1;i<=n+2;i++)
        fac[i]=fac[i-1]*i%mod;
    for(int i=0;i<=n+2;i++)
        prv[i]=mum[i]=1;
    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=1;i<=q;i++){
        while(l>b[i].l) add(--l);
        while(r<b[i].r) add(++r);
        while(r>b[i].r) del(r--);
        while(l<b[i].l) del(l++);
        int K=0,invf=1;
        for(int j=1;j<bl(b[i].x-1);j++)
            K+=pre[j], invf=invf*prv[j]%mod;
        for(int j=st(b[i].x-1);j<b[i].x;j++)
            K+=ton[j], invf=invf*mum[j]%mod;
        ans[b[i].id]=fac[K]*qpow(invf,mod-2)%mod;
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

泪点解析：出题人专门放了 8 个 anti_fenwick 测试点来卡 log。让我们感谢良心出题人。