202503021944 HDU-4000 Fruit Ninja

快速求小于当前数的个数 Fruit Ninja

title: 题目
![[Pasted image 20220802100243.png]]

title: input
2
6
1 3 2 6 5 4
5 
3 5 2 4 1
 

title: output
Case #1: 10
Case #2: 1
 

title: 思路
$$
\begin{align*}
& a[x] < a[z] < a[y] 且 x < y < z \\
 
& (x < y < z) \\
& == (x < y < z) + (x < z < y) - (x < z < y)\\
& == (x < *) - (x < z < y)\\
\end{align*}
$$
根据x来找, 找后面比这个数大的个数n, 求 $C^{2}_{n}$
求 $(x < z < y)$ 则把当前数当做z, 小于z的个数\*大于z的个数即可。
 
**小于当前数的个数: **`sum1 = sum(a[i]);`
**大于当前数的个数：** `(n - a[i]) - (i - 1 - sum1)` 前一项是所有大于当前数的个数, 后一项是之前计算过的大于当前数的个数, 作差即是后面大于该数的个数。
**(x < z < y): ** `大于当前数的个数 \* 小于当前数的个数`
**(x < *): ** `大于当前数的个数  * （大于当前数的个数 - 1） / 2`
 
如何快速求小于当前数的个数？ 用树状数组。
 

title:代码
~~~ c ++
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int readInt()
{
    int t;
    scanf("%d", &t);
    return t;
}
 
//------- Coding Area ---------//
const int N = 5e5 + 10, MOD = 1e8 + 7;
int t[N], a[N], n;
 
int lowbit(int i)
{
    return i & -i;
}
 
void add(int i)
{
    for (i; i <= n; i += lowbit(i))
        t[i]++;
}
 
int sum(int i)
{
    int s = 0;
    for (i; i; i -= lowbit(i))
        s += t[i];
    return s;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int kase = 1; kase <= T; kase++)
    {
        memset(t, 0, sizeof t);
        cin >> n;
        long long res = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            int sum1 = sum(a[i] - 1); // 小于当前数的个数
            add(a[i]);
            int t = (n - a[i]) - (i - sum1 - 1); // 大于当前数的个数
            res += (long long)t * (t - 1) / 2 - (long long)sum1 * t;
            res = (res % MOD + MOD) % MOD;
        }
        cout << "Case #" << kase << ": " << res << "\n";
    }
}
 
~~~