題意：給你一些不同數，求滿足a < b < c的有多少組。
代碼：
[cpp]
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 20010;
struct people{
int id,num;
}pp[N];
struct newpeople{
int id,num;
}newpp[N];
int dit[N];
bool cmp(people a,people b){
return a.num < b.num;
}
bool cmp2(newpeople a,newpeople b){
return a.id < b.id;
}
int lowbit(int x){
return x & (-x);
}
int sum(int x){
int s = 0;
while(x < N){
s += dit[x];
x += lowbit(x);
}
return s;
}
void update(int x){
while(x > 0){
dit[x] += 1;
x -= lowbit(x);
}
}
int main(){
int numcase;
scanf("%d",&numcase);
while(numcase--){
int n;
scanf("%d",&n);
memset(dit,0,sizeof(dit));
for(int i = 1; i <= n; ++i){
scanf("%d",&pp[i].num);
pp[i].id = i;
}
sort(pp+1,pp+n+1,cmp);
for(int i = 1; i <= n; ++i){
newpp[i].id = pp[i].id;
newpp[i].num = i;
}
sort(newpp+1,newpp+n+1,cmp2);
int fbig[N],fsmall[N],bbig[N],bsmall[N];
for(int i = 1; i <= n; ++i){
int x = newpp[i].num;
fbig[i] = sum(x);
fsmall[i] = i - 1 - fbig[i];
bbig[i] = n - x - fbig[i];
bsmall[i] = x - 1 - fsmall[i];
update(x);
}
__int64 ans = 0;
for(int i = 1; i <= n; ++i){
ans += (fbig[i] * bsmall[i]);
ans += (fsmall[i] * bbig[i]);
}
printf("%I64d\n",ans);
}
return 0;
}
