P4528 [CTSC2008] 图腾 做题笔记

前言

感觉是最近做过最有意思的一道容斥计数啊，来补篇笔记。

思路

下文将满足 $1\leq a<b<c<d\leq n$，且 $p_a,p_b,p_c,p_d$ 从小到大的排名在这四个数中依次为 $1\leq i,j,k,l\leq 4$ 的四元组 $(a,b,c,d)$ 简称为 $\text{ijkl}$，若排名不确定则用 $\text x$ 代替。例：$\text{1423}$，$\text{1x2x}$。

简单概括一下题意：求 $1$ 到 $n$ 的排列中 $\text{1324}$ 的数量减去 $\text{1243}$ 与 $\text{1432}$ 数量之和的结果。

看见这几个奇形怪状的东西第一反应是拿什么数据结构科技直接跑去暴力求（毕竟 $\text{1234}\ \text{4321}$ 这种东西很方便就能求出来，这几个也应该有办法对吧），但并没有什么科技能方便我们求出来。于是只能考虑容斥。

我们把要求的东西列一个式子，然后看看能不能转换成更好求的形式：

$\text{1324}-\text{1243}-\text{1432}$

$=(\text{1x2x}-\text{1423})-(\text{12xx}-\text{1234})-(\text{14xx}-\text{1423})$

$=\text{1x2x}-\text{12xx}+\text{1234}-\text{14xx}$

$=\text{1x2x}-\text{1xxx}+\text{13xx}+\text{1234}$

转换成这样之后，我们发现不仅式子里多出来了 $\text{1xxx}$ 和 $\text{1234}$ 两个随便秒的东西，剩下两项的限制也比较松，瞬间就可做了许多。

于是对于每个 $i$，我们先用树状数组预处理出 $j<i,p_j<p_i$ 的个数 $L_i$，$j>i,p_j>p_i$ 的个数 $R_i$，左边小于自己的 $p_j$ 的下标和（即 $\sum j\times [p_j<p_i](j<i)$）$lsum_i$，以及左边小于自己的 $p_j$ 的和（即 $\sum p_j\times [p_j<p_i](j<i)$）$lsump_i$，这些东西都是计划的一部分。

1xxx、1234

比较容易，对于 $\text{1xxx}$，枚举 $1$ 的位置 $i$，则答案显然为 $C^{R_i}_3=\frac{n\times (n-1)\times (n-2)}{6}$；对于 $\text{1234}$，设 $f_{i,j}$ 为以 $i$ 结尾、长度为 $j$ 的上升子序列个数，则枚举 $4$ 的位置 $i$，$f_{i,4}$ 即为答案，同样用树状数组扫一下即可。

1x2x

首先枚举 $2$，钦定 $2$ 的位置为 $i$，则左边正好有 $L_i$ 个备选的 $1$。

第二个 $\text x$ 的方案数显然为 $n-i$，设第一个 $\text x$ 的位置为 $j$，如果取答案为 $L_i\times (i-1)\times (n-i)$，则有两种情况会被重复计算：$j$ 在 $1$ 左边或等于 $i$ 或 $p_j<p_i$。可以容斥，设 $1$ 的位置为 $k$，发现如果对每个 $1$ 在答案里减掉 $k$ 就可以剔除所有的第一种情况和第二种情况中第一个 $\text x>p_i$ 的情况。于是我们只要再减一个 $1、\text x$ 都来自 $L_i$ 的情况，即 $C^{L_i}_2=\frac{L_i\times (L_i-1)}{2}$。

于是这种情况的总数就是 $[L_i\times (i-1)-lsum_i-\frac{L_i\times (L_i-1)}{2}]\times (n-i)$。

13xx

这次我们枚举 $3$，则左边有 $L_i$ 个备选的 $1$，同时我们在两个 $\text x$ 中钦定一个有 $R_i$ 种备选的 $4$，则剩下一个有 $p_i-1-L_i$ 种备选的 $2$。

直接取答案为 $L_i\times R_i\times(p_i-1-L_i)$，会重复算上选出的 $2$ 比 $1$ 小的情况。

我们可以搞一个有些人类智慧的容斥，暂时不管 $2$ 在 $3$ 右边的限制，这样就是 $L_i\times R_i\times (p_i-1)$，再对每个 $j<i,p_j<p_i$ 减去一个 $p_j$，即对总答案减少上面算过的 $lsump_i$。设 $1$ 位置为 $j$，$2$ 位置为 $k$，我们就可以直接排除掉 $k<i,p_k\leq p_j$ 和 $k>i,p_k<p_j$，聪明的你一定发现了第二种其实就是 $2<1$，再减去第一种没有包括的 $k<i,p_k>p_j$，即所有 $C^{L_i}_{2}=\frac{L_i\times (L_i-1)}{2}$ 个 $p_j<p_k<p_i$ 的有序对 $(j,k)$。

最后的总数是 $L_i\times R_i\times (p_i-1)-lsump_i-\frac{L_i\times (L_i-1)}{2}$。

至此，我们已经算出来了需要的所有四元组的个数，这道题就做完了。

代码

发现题目的模数是 $2$ 的整数次方，于是直接 unsigned int 自然溢出后再模就可以，省了不少麻烦。

constexpr int N = 2e5+5;

int n,p[N];
uint Is[N][5],lsum[N],lsump[N],L[N],R[N];

struct BIT{
    #define lb(x) ((x)&(-(x)))
    uint tr[N];
    int mk[N],now = 0;
    inline void clr(){now++;}
    inline void add(int x,uint v){
        while(x<=n){
            if(mk[x]^now)	mk[x] = now,tr[x] = 0;
            tr[x]+=v,x+=lb(x);
        }
    }
    inline uint query(int x){
        uint res = 0;
        while(x){
            if(!(mk[x]^now))	res+=tr[x];
            x-=lb(x);
        }
        return res;
    }
    inline uint query(int l,int r){return query(r)-query(l-1);}
}bit;

void solve(){
    read(n);
    for(int i=1;i<=n;i++)    read(p[i]);
    for(int i=1;i<=n;i++){
        L[i] = Is[i][2] = bit.query(1,p[i]-1);
        bit.add(p[i],1);
    }
    bit.clr();
    for(int i=n;i>=1;i--){
        R[i] = bit.query(p[i]+1,n);
        bit.add(p[i],1);
    }
    bit.clr();
    for(int j=3;j<=4;j++){
        for(int i=1;i<=n;i++){
            Is[i][j] = bit.query(1,p[i]-1);
            bit.add(p[i],Is[i][j-1]);
        }
        bit.clr();
    }
    for(int i=1;i<=n;i++){
        lsum[i] = bit.query(1,p[i]-1);
        bit.add(p[i],i);
    }
    bit.clr();
    for(int i=1;i<=n;i++){
        lsump[i] = bit.query(1,p[i]-1);
        bit.add(p[i],p[i]);
    }
    uint ans = 0;
    for(int i=1;i<=n;i++){
        ans = ans+(L[i]*(i-1)-lsum[i]-((ull)L[i]*(L[i]-1)/2))*R[i];
        ans = ans-((ull)R[i]*(R[i]-1)*(R[i]-2)/6);
        ans = ans+Is[i][4];
        ans = ans+(R[i]*(L[i]*(p[i]-1)-lsump[i]-(ull)L[i]*(L[i]-1)/2));
    }
    cout<<ans%16777216;
}