题目链接：http://icpc.njust.edu.cn/Problem/Hdu/2492/
题目大意：给定一个序列，求长度为三的子序列（a,b,c）使得a<b<c或a>b>c，求这样的序列的个数；只要对于每一个位置的数，用树状数组维护前缀和，求出该位置前面比他大的数的个数和比他小的个数，再用另一个树状数组从末位向前维护该位置后面比他大的数的格式和比他小的数的个数。最终 前大*后小+前小*后大 对n个位置求和即可。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define scand(x) scanf("%llf",&x) 12 #define f(i,a,b) for(int i=a;i<=b;i++) 13 #define scan(a) scanf("%d",&a) 14 #define dbg(args) cout<<#args<<":"<<args<<endl; 15 #define pb(i) push_back(i) 16 #define ppb(x) pop_back(x) 17 #define inf 0x3f3f3f3f 18 #define maxn 100010 19 int n,m,t; 20 int a[maxn],c[maxn]; 21 int lowbit(int x) 22 { 23 return x&(-x); 24 } 25 int query(int x) 26 { 27 int ans=0; 28 for(int i=x;i;i-=lowbit(i)) 29 { 30 ans+=c[i]; 31 } 32 return ans; 33 } 34 void update(int x,int C) 35 { 36 for(int i=x;i<=100005;i+=lowbit(i)) 37 { 38 c[i]+=C; 39 } 40 } 41 int l1[maxn],r1[maxn],l2[maxn],r2[maxn]; 42 int main() 43 { 44 //freopen("input.txt","r",stdin); 45 //freopen("output.txt","w",stdout); 46 std::ios::sync_with_stdio(false); 47 scan(t); 48 while(t--) 49 { 50 scan(n); 51 f(i,1,n)scan(a[i]); 52 mem(c,0); 53 f(i,1,n) 54 { 55 l1[i]=query(a[i]-1);//查询左侧比a[i]小的数的个数 56 l2[i]=i-1-l1[i];//查询左侧比a[i]大的数的数量 57 update(a[i],1); 58 } 59 mem(c,0); 60 for(int i=n;i>=1;i--) 61 { 62 r1[i]=query(a[i]-1);//右侧比a[i]小的数的个数 63 r2[i]=n-i-r1[i];//右侧比a[i]大的数的个数 64 update(a[i],1); 65 } 66 ll ans=0; 67 f(i,1,n) 68 { 69 ans+=l1[i]*r2[i]+l2[i]*r1[i]; 70 } 71 pf("%lld ",ans); 72 } 73 }