题解：P4528 [CTSC2008] 图腾

前言

神题 orz。

Solution

约定： 表示排名分别为 ，，， 的四元组的数量。

形如 则表示第一个元素排名为 ，其余元素排名不做要求，形如 则表示第一个元素排名为 ，第二个元素排名为 ，其余元素排名不做要求，以此类推。

题目要求的是这个：

那么它等于：

现在我们就只需要求 ，，， 这四个值就行了。

约定： 表示 前面比 小的元素个数， 表示 前面比 大的元素个数， 表示 后面比 小的元素个数， 表示 后面比 大的元素个数（prefixsmall，prefixbig，suffixsmall，suffixbig）。

的求法：固定 ，枚举第一个 ，则 。
即固定 的位置 ，在 后面选一个比 大的元素；第一个 的排名必须比 大，所以在 的前面，先选一个比 大的元素 ，再在 前面选一个比 小的元素，减去选了两个比 大的元素的方案。

的求法：固定 ，枚举 ，则 。
即固定 的位置 ，在 后面选一个比 大的元素；在 的前面，先选一个比 小的元素 ，再在 前面选一个比 小的元素。

的求法：固定 ，则 。
即固定 的位置 ，在 的后面，选 3 个比 大的。

的求法：固定 ，则 。
即固定 的位置 ，在 后面选一个比 大的元素，再选一个比 小的元素 ，再选一个比 小的元素（注意该元素位置不定），减去两个被选的比 小的元素都在 后面的方案。

上述式子中，所有内层枚举 的求和都可以用树状数组优化掉。

时间复杂度

。

Code

#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
namespace FastIO
{
    template <typename T>
    inline void read(T &x)
    {
        short neg = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch))
            if (ch == '-')
                neg = -1;
        x = ch - '0';
        while (ch = getchar(), isdigit(ch))
            x = (x << 3) + (x << 1) + (ch ^ '0');
        x *= neg;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args &...args)
    {
        read(x);
        read(args...);
    }
    template <typename T>
    inline void read(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            read(*(begin + i));
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T, typename... Args>
    inline void write(T x, Args... args)
    {
        write(x);
        putchar(' ');
        write(args...);
    }
    template <typename T>
    inline void write(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            write(*(begin + i)), putchar(' ');
    }
}
using namespace FastIO;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
class BIT
{
private:
    uLL tree[200005];
    int sz;

public:
    void init(int n)
    {
        nmf(i, 1, n) tree[i] = 0;
        sz = n;
    }
    void upd(int x, int val)
    {
        while (x <= sz)
        {
            tree[x] += val;
            x += (x & -x);
        }
    }
    int query(int x)
    {
        if (x > sz)
            x = sz;
        int ret = 0;
        while (x > 0)
        {
            ret += tree[x];
            x -= (x & -x);
        }
        return ret;
    }
};
int n;
int a[200005];
uLL ps[200005], pb[200005], ss[200005], sb[200005];
const uLL mod = 16777216;
uLL ans;
BIT tr1, tr2;
namespace Initialize
{
    void init()
    {
        tr1.init(n);
        tr2.init(n);
        nmf(i, 1, n)
        {
            ps[i] = tr1.query(a[i] - 1);
            pb[i] = tr2.query(n - (a[i] + 1) + 1);
            tr1.upd(a[i], 1);
            tr2.upd(n - a[i] + 1, 1);
        }
        tr1.init(n);
        tr2.init(n);
        ref(i, n, 1)
        {
            ss[i] = tr1.query(a[i] - 1);
            sb[i] = tr2.query(n - (a[i] + 1) + 1);
            tr1.upd(a[i], 1);
            tr2.upd(n - a[i] + 1, 1);
        }
    }
}
void solve()
{
    read(n);
    read(a + 1, a + 1 + n);
    Initialize::init();
    tr1.init(n);
    tr2.init(n);
    nmf(i, 1, n)
    {
        ans += sb[i] * ((tr2.query(n - (a[i] + 1) + 1)) - (pb[i] * (pb[i] - 1) / 2));
        ans += sb[i] * (tr1.query(a[i] - 1));
        ans -= sb[i] * (sb[i] - 1) * (sb[i] - 2) / 6;
        tr1.upd(a[i], ps[i]);
        tr2.upd(n - a[i] + 1, i - 1);
    }
    tr1.init(n);
    ref(i, n, 1)
    {
        ans += sb[i] * (tr1.query(a[i] - 1) - ((ss[i]) * (ss[i] - 1) / 2));
        tr1.upd(a[i], a[i] - 1);
    }
    ans = ans % mod;
    write(ans), putchar('\n');
    return;
}
signed main()
{
    solve();
    return 0;
}