[CTSC2008] 图腾

Description

$\rm Link$

Solution

做完这道题感觉对树状数组偏序计数有了全新的认识...🚀

为了方便，我们用一个 $4$ 的排列 $\text{abcd}$ 来表示该相对高度关系下的四元组数量。
题目要求的就是 $1324-1243-1432$ 。我们稍微变形（设 $\rm x$ 表示在不重复的情况下该位任意填）。

$\begin{aligned} &1324-1243-1432\\ =&1\rm x2x-1423-(12xx-1234)-(14xx-1423)\\ =&1\rm x2x-12xx-14xx+1234\\ =&1\rm x2x-1xxx+13xx+1234 \end{aligned}$

现在让我们逐个分析如何求解。记 $L_i=\sum_{j<i}[a_j<a_i],R_i=\sum_{j>i}[a_j>a_i]$ 。

考虑 $1\rm xxx$ 。这个就是 $\sum\limits_{i=1}^{n}\binom{R_i}{3}$ 。

考虑 $1234$ 。枚举 $3$ 的位置 $i$ ，那么 $4$ 的方案数是 $R_i$，每个满足 $a_j<a_i,j<i$ 的 $j$ 可以做 $2$ 号位置，并且此时 $1$ 号位置的方案数是 $L_j$。拿树状数组维护一下就可以了。

考虑 $1\rm x2x$ 。枚举 $2$ 的位置 $i$，那么右边的 $\rm x$ 的方案数是 $R_i$ 。只考虑左边的方案数。分析左边的问题本质，就是在给定 $i$ 的情况下，找到 $j,k$ ，满足

• $j < k < i$
• $a_j < a_i < a_k$

我们先只钦定 $j<i,k<i a_j<a_i$ 这三个条件。此时的方案数为 $L_i(i-1)$。
这样子明显多算了。事实上，多算的贡献恰可以分为两个部分。

• $k\leq j$ 。此时可以发现，对于每个满足 $a_j<a_i,j<i$ 的 $j$ 而言，都有一个 $j$ 的贡献需要减掉。这部分的贡献是两维偏序，我们顺序枚举去掉一维，树状数组解决第二维，就可以快速计算。
• $k>j,a_k<a_i$。这个的方案数就是 $\binom{L_i}{2}$ 。

考虑 $13\rm xx$。类似的，枚举 $3$ 的位置 $i$ ，$4$ 的方案数就是 $R_i$ 。我们只需要考虑 $132$ 的方案数。这个子问题的偏序关系是

• $j<i<k$
• $a_j<a_k<a_i$

同样，我们先只钦定 $i<k,a_j< a_k<a_i$ ，那么对于每个 $i<k,a_k<a_i$ 的 $k$ ，贡献是 $a_k-1$。这部分贡献显然可以用树状数组快速计算。
这样子明显也多算了。多算了 $j> i$ 的贡献，而这部分贡献恰可以表示为 $\binom{R_i}{2}$ 。

感觉容斥部分最妙的就是通过钦定，使得原先在不同侧的限制转化为同侧（既指下标意义上的左右，也指值域意义上的上下），同侧的限制可以方便的用组合数计算。通过钦定，让一个有多个偏序关系限制的计数转化为若干个方便的 $2,3$ 维偏序关系的计数，非常 nb。

上述 $\rm Solution$ 的第四类如果考虑重点不是 $k$ 而是 $j$ ，那么与第三类的叙述就非常接近了。所以本质上应该是一样的，优化的方法也就是一样的。

复杂度 $\mathcal{O}(n\log_2n)$

Code

const int N = 2e5 + 5, mod = 16777216;
using namespace std;
int n;
int a[N], L[N], R[N];
struct BIT{
#define lowb(x) (x & -x)
    long long t[N]; //various
    void Add(register int p, int v = 1){
        while(p <= n) t[p] += v ,p += lowb(p);
    }
    long long Get(register int p){
        long long ret = 0;
        while(p) ret += t[p] ,p -= lowb(p);
        return ret;
    }
    void clr(){
        memset(t, 0, sizeof t);
    }
#undef lowb
}bit;
int main(){

    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];
    for(int i = 1; i <= n; ++i)
        L[i] = bit.Get(a[i]), bit.Add(a[i]);
    bit.clr();
    for(int i = n; i >= 1; --i)
        R[i] = bit.Get(a[i]), bit.Add(a[i]);
    bit.clr();

    int ans = 0;

    // 1xxx
    for(int i = 1; i <= n; ++i){
        int v = n - i - R[i];
        ans = (ans + mod -  1ll * v * (v - 1) / 2 * (v - 2) / 3 % mod) % mod;
    }

    // 13xx
    for(int i = n; i >= 1; --i){
        int v4 = n - i - R[i], vo = bit.Get(a[i]);
        vo = (vo + mod - 1ll * R[i] * (R[i] + 1) / 2 % mod) % mod;
        ans = (ans + 1ll * vo * v4 % mod) % mod;
        bit.Add(a[i], a[i]);
    }
    bit.clr();

    // 1x2x
    for(int i = 1; i <= n; ++i){
        int vr = n - i - R[i], vl = L[i] * (i - 1) % mod;
        vl = (vl + mod - 1ll * L[i] * (L[i] - 1) / 2 % mod) % mod;
        vl = (vl + mod - bit.Get(a[i])) % mod;
        ans = (ans + 1ll * vl * vr % mod) % mod;
        bit.Add(a[i], i);
    }
    bit.clr();

    // 1234
    for(int i = 1; i <= n; ++i){
        int v4 = n - i - R[i], vo = bit.Get(a[i]);
        ans = (ans + 1ll * v4 * vo % mod) % mod;
        bit.Add(a[i], L[i]);
    }

    cout << ans << endl;

    return 0;
}