题解：P16019 [ICPC 2021 NAC] Permutation CFG

· · 题解

题意简述

排列中的符号 x 会按排列顺序展开为所有不超过 x 的符号。从 n 开始展开 s 次，询问最终序列某个前缀中符号 k 的出现次数。

解题思路

记 F_d(x) 为符号 x 展开 d 次得到的序列，F_0(x) 只含一个 x。若排列第 i 项为 a_i，则 F_d(x) 由所有满足 a_i\le x 的 F_{d-1}(a_i) 按 i 递增的顺序拼接而成。

先计算完整块的长度。每次展开都对前一层长度做一次关于 x 的前缀和，因此：

|F_d(x)|=\binom{x+d-1}{d}

类似地，当 d\ge1 且 k\le x 时，完整序列中 k 的出现次数为：

\operatorname{cnt}_d(x,k)=\binom{x-k+d-1}{d-1}

回答 F_d(x) 的前缀询问时，先按排列顺序找到前缀末尾所在的子块。此前的子块全部计入答案，末尾子块只递归处理剩余前缀。每次递归使 d 减少 1，深度至多为 5。

为了快速定位子块，按数值建立可持久化线段树。第 x 个版本包含数值 1 到 x，每个数值 y 被插入排列位置 \operatorname{pos}_y。于是叶子从左到右仍保持原排列顺序，而版本本身已经过滤掉大于 x 的符号。

在线段树每个结点中，对 0\le d\le4 保存：

\sum_y\binom{y+d-1}{d}

它正是对应子树内所有 F_d(y) 的长度和。沿树比较左子树长度，便能在 O(\log n) 时间内找到前缀末尾所属的块，并同步扣除它之前的总长度。

还需统计末尾块之前所有完整块的贡献。假设这些块的符号为 y，当前要统计 F_d(y) 中的 k。令 r=d-1，单块贡献为：

\binom{y-k+r}{r}

不必保存 y 的幂次和。使用广义 Vandermonde 恒等式：

\binom{y-k+r}{r} =\sum_{j=0}^{r}\binom{y}{j}\binom{r-k}{r-j}

这里上指标 r-k 可以为负数，仍按广义组合数的乘法递推定义。由于 r\le3，线段树结点只需额外保存：

\sum_y\binom{y}{j}

其中 0\le j\le3。

设末尾块位于排列位置 p。完整块必须同时满足 k\le y\le x 与 \operatorname{pos}_y<p。用版本 x 减去版本 k-1，再查询位置前缀 [1,p-1]，即可取得上述四个二项式矩并还原全部贡献。

块长度只用于和询问前缀比较。超过 long long 安全上界的长度统一截断为 inf，不会改变线段树上的定位结果。二项式矩和中间乘积使用 __int128 保存。

建立全部版本需要 O(n\log n) 时间和空间。每次询问递归至多 s 层，每层进行一次定位和一次前缀查询，时间复杂度为 O(s\log n)。

正确性证明

长度公式的初值为 |F_0(x)|=1。一次展开会恰好拼接 F_{d-1}(1) 到 F_{d-1}(x) 各一次，所以组合数上指标求和恒等式给出 |F_d(x)|=\binom{x+d-1}{d}。出现次数公式同理成立。

第 x 个持久化版本中的叶子集合恰好对应所有不超过 x 的符号，叶子顺序恰好是这些符号在排列中的顺序。节点保存的权值又等于各子块长度，因此树上定位得到的就是第一个未被查询前缀完整覆盖的子块。

版本差精确筛出 k\le y\le x，位置前缀精确筛出末尾块之前的符号。Vandermonde 恒等式逐个 y 还原 \binom{y-k+r}{r}，所以 count_full 不重不漏地统计全部完整块。

最后，对递归深度归纳。当前层先正确计入所有完整块，再只递归到唯一的末尾块；后续块不属于前缀。深度为 0 时直接判断唯一符号是否等于 k。因此每次询问返回的都是指定前缀中 k 的准确出现次数。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using i128=__int128;
const int N=100005;
const int M=N*19;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct node
{
    int l,r;
    ll sum[5];
    i128 c[4];
}tr[M];
int n,tot;
int rt[N],a[N],pos[N];
i128 C(ll n,int m)
{
    i128 res=1;
    for(int i=1;i<=m;i++)res=res*(n-i+1)/i;
    return res;
}
int update(int pre,int l,int r,int x,int val)
{
    int u=++tot;
    tr[u]=tr[pre];
    if(l==r)
    {
        for(int i=0;i<=4;i++)tr[u].sum[i]=min((i128)inf,C(val+i-1,i));
        for(int i=0;i<=3;i++)tr[u].c[i]=C(val,i);
        return u;
    }
    int mid=(l+r)>>1;
    if(x<=mid)tr[u].l=update(tr[pre].l,l,mid,x,val);
    else tr[u].r=update(tr[pre].r,mid+1,r,x,val);
    for(int i=0;i<=4;i++)tr[u].sum[i]=min(inf,tr[tr[u].l].sum[i]+tr[tr[u].r].sum[i]);
    for(int i=0;i<=3;i++)tr[u].c[i]=tr[tr[u].l].c[i]+tr[tr[u].r].c[i];
    return u;
}
int kth(int u,int l,int r,int d,ll &k)
{
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(k<=tr[tr[u].l].sum[d])return kth(tr[u].l,l,mid,d,k);
    k-=tr[tr[u].l].sum[d];
    return kth(tr[u].r,mid+1,r,d,k);
}
void query(int u,int v,int l,int r,int x,i128 res[4])
{
    if(x<l)return;
    if(r<=x)
    {
        for(int i=0;i<=3;i++)res[i]+=tr[u].c[i]-tr[v].c[i];
        return;
    }
    int mid=(l+r)>>1;
    query(tr[u].l,tr[v].l,l,mid,x,res);
    if(x>mid)query(tr[u].r,tr[v].r,mid+1,r,x,res);
}
ll count_full(int d,int x,int k,int p)
{
    if(d==0)return pos[k]<p;
    i128 v[4]={};
    query(rt[x],rt[k-1],1,n,p-1,v);
    int r=d-1;
    i128 res=0;
    for(int i=0;i<=r;i++)res+=C(r-k,r-i)*v[i];
    return res;
}
ll solve(int d,int x,int k,ll len)
{
    if(k>x)return 0;
    if(d==0)return x==k;
    int p=kth(rt[x],1,n,d-1,len);
    return count_full(d-1,x,k,p)+solve(d-1,a[p],k,len);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int s,q;
    cin>>n>>s>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pos[a[i]]=i;
    }
    for(int i=1;i<=n;i++)rt[i]=update(rt[i-1],1,n,pos[i],i);
    while(q--)
    {
        int k;
        ll len;
        cin>>k>>len;
        cout<<solve(s,n,k,len)<<'\n';
    }
    return 0;
}