问题描述

小布的团队在山洞里发现了一幅巨大的壁画,壁画上被标记出了 $N$ 个点,经测量发现这 $N$ 个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这 $N$ 个点的相对位置有关,因此不妨设坐标分别为 $(1, y_1) , (2, y_2), …, (n, y_n)$ 其中 $y_1$ 到 $y_n$ 是 $1$ 到 $N$ 的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾,其中闪电图腾的定义图示如下(图腾的形式只与 4 个纵坐标值的相对大小排列顺序有关):
闪电图腾
崇拜高山的部落有两个氏族,因而山峰图腾有如下两种形式,左边为 A 类,右边为 B 类(同样,图腾的形式也都只与 4 个纵坐标值的大小排列顺序有关):
A山峰图腾
小布的团队希望知道,这 $N$ 个点中两个部落图腾数目的差值。因此在本题中,你需要帮助小布的团队编写一个程序,计算闪电图腾数目减去山峰图腾数目的值,由于该值可能绝对值较大,本题中只需输出该值对 $16777216$ 的余数。

输入

第一行包含一个整数 $N$ ($N≤200000$) 为点的数目。
接下来一行包含 $N$ 个整数,分别为 $y1,y2,…,yn$。

输出

仅包含一个数,表示闪电图腾数目与山峰图腾数目的差值对 16777216 的余数。

思路

超级神仙的一道题。

我们先考虑所有的六种情况 $1234,1243,1324,1342,1423,1432$,然后题目要求的是 $1324-1243-1432$ 的数量。然后可以发现形如 $1xxx,12xx,13xx,1x2x,1234,1243$ 的这些情况是可以求出来的(可能还有其他的情况)。然后就将题目要求的情况变换成我们能求出的情况:
$1324-1243-1432$
$=(1x2x-1423)-(12xx-1234)-(14xx-1423)$
$=1x2x-12xx+1234-14xx$
$=1234+13xx+1x2x-1xxx$

我们设 $l_i=\sum_{j=1}^{i}[a_j<a_i]$,$r_i=\sum_{j=i}^{n}[a_j<a_i]$

$1xxx$ 的数量比较好求,就是: $$\sum_{i=1}^{n} {n-r_i-i\choose3}$$
$1234$ 的数量也不难,枚举 $3$ 的位置 $i$,那么 $4$ 的情况数就是 $n-r_i-i$,$12$ 的情况数就是 $\sum_{j=1}^{i} ([a_j<a_i] l_i)$,总数量就是:$$\sum_{i=1}^{n} (n-r_i-i)*\sum_{j=1}^{i} ([a_j<a_i] l_i)$$
$13xx$ 的数量同样枚举 $3$ 的位置 $i$,那么 $4$ 的情况数还是 $(n-r_i-i)$,$132$ 的情况数可以先计算 $12$ 的情况数 $\sum_{j=i}^{n}([a_j<a_i] (a_j-1))$ 然后减去 $12$ 同时在 $3$ 右边的情况 ${r_i}\choose{2}$,总数量就是:$$\sum_{i=1}^{n}(n-r_i-i)*[\sum_{j=i}^{n}([a_j<a_i] (a_j-1))- {r_i \choose 2}]$$

$1x2x$ 的数量可以枚举 $2$ 的位置 $i$,那么 $2$ 后面 $x$ 的情况数就是 $(n-r_i-i)$,$1×2$ 的情况数先可以计算 $1x$ 和 $x1$ 的情况数 $l_i*(i-1)$,然后减去两个数都比 $2$ 小的情况数 ${l_i \choose 2}$,最后减去 $x$ 在 $1$ 前的情况数 $\sum_{j=1}^{i} ([a_j<a_i]j)$,总数量就是:$$\sum_{i=1}^{n} (n-r_i-i) * [l_i*(i-1)-{l_i \choose 2}-\sum_{j=1}^{i} ([a_j<a_i]j)] $$
所有这些东西都可以用树状数组在 $O(n\log n)$ 内维护。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 200005
#define P 16777216
#define rint register int
#define LL long long
using namespace std;

int n, sum1, sum2, sum3, sum4, y[MAXN], l[MAXN], r[MAXN], t[MAXN];

void add(int x, int y)
{
    for (; x <= n; x += (x & -x))
        t[x] = (t[x] + y) % P;
}

int ask(int x)
{
    int ans = 0;
    for (; x; x -= (x & -x))
        ans = (ans + t[x]) % P;
    return ans;
}

int comb(int x, int y)
{
    LL up = 1, down = 1;
    for (rint i = 0; i < y; ++i)
        up *= (x - i), down *= (i + 1);
    return up / down % P;
}

int main()
{
    scanf("%d", &n);
    for (rint i = 1; i <= n; ++i)
        scanf("%d", &y[i]);
    for (rint i = 1; i <= n; ++i)
    {
        l[i] = ask(y[i]);
        r[i] = y[i] - l[i] - 1;
        add(y[i], 1);
    }
    for (rint i = 1; i <= n; ++i)
    {
        sum1 = (sum1 + comb(n - r[i] - i, 3)) % P;
    }
    memset(t, 0, sizeof(t));
    for (rint i = 1; i <= n; ++i)
    {
        sum2 = (sum2 + 1LL * (n - r[i] - i) * ask(y[i]) % P) % P;
        add(y[i], l[i]);
    }
    memset(t, 0, sizeof(t));
    for (rint i = n; i >= 1; --i)
    {
        sum3 = (sum3 + 1LL * (n - r[i] - i) * (ask(y[i]) - comb(r[i], 2) + P) % P) % P;
        add(y[i], y[i] - 1);
    }
    memset(t, 0, sizeof(t));
    for (rint i = 1; i <= n; ++i)
    {
        sum4 = (sum4 + 1LL * (n - r[i] - i) * (1LL * (i - 1) * l[i] - comb(l[i], 2) - ask(y[i])) % P + P) % P;
        add(y[i], i);
    }
    printf("%d\n", (sum2 + sum3 + sum4 - sum1 + P) % P);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注