题目链接：https://www.luogu.org/problemnew/show/P1637
BIT + 离散化。
读题得数据规模需离散化。BIT开不到longint这么大的数组。
对于题目所求的三元上升子序列，我们可以通过枚举1~n作为中间数，记录左边比他小的个数L[i]，右边比他大的个数R[i]，那么对于第i个中间数就有L[i]*R[i]个子序列。
L，R可以通过树状数组求得。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3e4 + 10;
int n, m, A[maxn], B[maxn], L[maxn], R[maxn];
class BIT{
public:
int tree[maxn];
void update(int pos, int val)
{
while(pos <= n)
{
tree[pos] += val;
pos += lowbit(pos);
}
}
int query(int pos)
{
int res = 0;
while(pos)
{
res += tree[pos];
pos -= lowbit(pos);
}
return res;
}
private:
int lowbit(int x)
{
return x & -x;
}
}T[2];
int Search(int x)
{
return lower_bound(B + 1, B + 1 + m, x) - B;
}
int main()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>A[i];
B[i] = A[i];
}
sort(B + 1, B + 1 + n);
m = unique(B + 1, B + 1 + n) - B - 1;
for(int i = 1; i <= n; i++)
A[i] = Search(A[i]);
for(int i = 1; i <= n; i++)
{
T[0].update(A[i], 1);
L[i] = T[0].query(A[i] - 1);
}
for(int i = n; i >= 1; i--)
{
T[1].update(A[i], 1);
R[i] = n - i - T[1].query(A[i]) + 1;
}
long long ans = 0;
for(int i = 2; i < n; i++) ans += L[i] * R[i];
cout<<ans;
return 0;
}
附：
离散化模板：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 10;
int n, m, A[maxn], B[maxn];
int Search(int x)
{
return lower_bound(B + 1, B + 1 + m, x) - B;
}
int main()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>A[i];
B[i] = A[i];
}
sort(B + 1, B + 1 + n);
m = unique(B + 1, B + 1 + n) - B - 1;
for(int i = 1; i <= n; i++)
A[i] = Search(A[i]);
for(int i = 1; i <= n; i++) cout<<A[i];
}