题目链接：https://codeforces.com/contest/1678/problem/C
题目大意：给一个长度为n的数组，求多少不同下标的四元组，满足a[1]<a[3]，a[4]<a[2]
比如 1，2，2，1? ? ? ? 1，3，4，2? ? ? ?1，4，3，2 都是满足题意的
思路：首先要用上求逆序对的思路，这题大概就是两个逆序对的结合
一共四个下标，最外层的for去枚举第三个下标 j，里面的for去枚举第一个下标 i ，只有a[i]<a[j]的时候，才去加
for(int j=n-1;j>=3;j--){
for(int i=j-2;i>=1;i--){
if(a[i]<a[j]){
sum+=; //sum是答案
}
}
}比如
5
3 5 4 7 2
当j=4（a[j]=7）的时候，i=2（a[i]=5）第一个满足
这时要找的就是 i+1 到 j-1 之间有多少比 j+1 到 n?之间的数小，这时就要用求逆序对的方法，一般是用树状数组来维护的，按j更新添加最右边的数，遍历 i?的时候，逐个更新最右边比a[i]小的数量
for(int j=n-1;j>=3;j--){
add(a[j+1],1); //树状数组更新添加最右边（j+1右边）的数
ans=0; //ans表示当前得j情况下，i向左边遍历，有的逆序对个数
for(int i=j-2;i>=1;i--){
ans+=get(a[i+1]-1); //get是查找已添加的数中，小于a[i+1]的数有多少
if(a[i]<a[j]){
sum+=ans; //ans=i~j中间有多少比j~n要大，sum+=ans
}
}
}代码?
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define int long long
#define lowbit(a) ((a)&(-a))
#define M 6005
int T,n;
int a[M],sum[M];
void add(int a,int b)
{
if(a==0) return;
for(int i=a;i<=n;i+=lowbit(i))
sum[i]+=b;
}
int get(int a)
{
if(a==0) return 0;
int ans=0;
for(int i=a;i;i-=lowbit(i))
ans+=sum[i];
return ans;
}
signed main()
{
cin.tie(nullptr)->sync_with_stdio(false);
cin>>T;
for(int k=1;k<=T;k++){
cin>>n;
for(int i=0;i<=n+1;i++) sum[i]=0;
int sum=0,ans=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=n-1;j>=3;j--){
add(a[j+1],1);
ans=0;
for(int i=j-2;i>=1;i--){
ans+=get(a[i+1]-1);
if(a[i]<a[j]){
sum+=ans;
}
}
}
cout<<sum<<endl;
}
return 0;
}
