2021 五星级挑战 132型序对

应大家的建议，我写点五星级题目的题解。

乍一看，写啥呢？没啥好写的，上随机数大法！中间省略了一大堆

经过了四次随机后，终于抽到了一道好题！

它就是$iai$第$100$号题目：132型序对

题目链接

先来讲下我初见这题时的想法：

暴力

暴力枚举$i,j,k$合法就$+1$，最后输出$ans$不就得了？就这还甲组题目？

继续往下滑，我看到了数据范围：$n \leq 20000$，不是$O(n^2)$优化，就是$O(n log n)$

这也是我第一次见到这么奇怪的数据范围，不大又不小。

开始想咋做。

暴力优化？不行，再怎么弄也不能从$O(n^3)$优化到$O(n^2)$啊

$cdq$分治？不对，这也不是一个偏序问题。

容斥

最后，我想到了容斥，用所有的减掉不符合要求的，

也就是用$n \times (n - 1) \times (n - 2)-a_{1,2,3}-a_{2,1,3}-a_{2,3,1}-a_{3,1,2}-a_{3,2,1}$（$a_{x,y,z}$的意思就是$xyz$型序对的数量）

我一看，这个$a_{1,2,3},a_{3.2.1}$写一个权值树状数组就$OK$了，但是其他三个呢？

好像跟$132$型序对一样难求啊！

想来想去，还是不知道正解，但是肯定是容斥啊！

之后，我想到了$a_{1,2,3}$是可以求的，而且它也是$1$开头的，那么我们是否可以用$a_{1,2,3}+a_{1,3,2}$减去$a-{1,2,3}$来得到呢？

显然是可以的，但是$a_{1,2,3}+a_{1,3,2}$是个什么鬼？

思考片刻后，我得到结论：$a_{1,2,3}+a_{1,3,2}$就是第一个数小，后面的数随便，只要比第一个数大即可了。（因为是排列啊）

这个东西也是很好求的。

下面先讲一下怎么求$a_{1,3,3}$（即第一个数最小，后面的比第一个数字大）

刚刚已经说了是权值树状数组。

那么我们就另树状数组的第$i$位$c[i]$为数字$i$出现的次数。

接着我们倒着循环一遍。每一次$c[a[i]]++$，在$i$后面并且比$a[i]$大的数字的数量

就是$c[a[i]+1] + c[a[i]+2] + ..... + c[n]$（即，比$a[i]$大一的数字加上比$a[i]$大二的数字一直加到$n$）

我们现在知道了在$i$后面并且比$i$大的数字出现了几次，如何算出$a_{1,3,3}$的出现次数呢？

我们可以先任选这sum$个数字中的$1$个，再选从另外$sum-1$个数字中选$1$个

方案数就是$sum \tmes (sum - 1)$，但是选的数字可能顺序不是递增的咋办

根据对称性，除以$2$即可得到递增的了

$a_{1,2,3}$也是这样求的

先求出在$a[i]$前比它小的，再求出在$a[i]$后比它大的，然后两者相乘（因为这次选啥都是序号递增的）即可。

代码很好写

#include <iostream>
using namespace std;
long long n, ans;
long long num[20010], pos[20010];
void add(long long x,long long v)
{
    for(; x <= n; x += x & (-x) ) num[x] += v;
}
long long sum(long long x)
{
    return (x == 0) ? 0 : sum(x - (x & (-x) ) ) + num[x];
}
int main()
{
    cin >> n;
    for(long long i = 1; i <= n; i ++) cin >> pos[i];    
    for(long long i = 1; i <= n; i ++)
    {
        long long L = sum(pos[i]);
        long long R = (n - pos[i]) - (i - 1 - L);
        ans += (R * (R - 1) / 2) - (R * L);
        add(pos[i], 1);
    }
    cout << ans << endl;   
    return 0;
}