求满足条件的三元组的个数，可以转换求一元组和二元组组成的满足条件的三元组的个数，且对于(x),(y,z),x > y,且x出现的p_x < p_y。
x可直接枚举O(n),此时需要往后查询二元组的个数，二元组可由两个一元组生成，实际上到这里就转换成了求两次逆序对而已。
#include <cmath> #include <cstdio> #include <cstdlib> #include <cassert> #include <cstring> #include <set> #include <map> #include <list> #include <queue> #include <string> #include <iostream> #include <algorithm> #include <functional> #include <stack> using namespace std; typedef long long ll; #define T int t_;Read(t_);while(t_--) #define dight(chr) (chr>='0'&&chr<='9') #define alpha(chr) (chr>='a'&&chr<='z') #define INF (0x3f3f3f3f) #define maxn (1000005) #define hashmod 100000007 #define ull unsigned long long #define repne(x,y,i) for(i=(x);i<(y);++i) #define repe(x,y,i) for(i=(x);i<=(y);++i) #define repde(x,y,i) for(i=(x);i>=(y);--i) #define repdne(x,y,i) for(i=(x);i>(y);--i) #define ri register int void Read(int &n){char chr=getchar(),sign=1;for(;!dight(chr);chr=getchar())if(chr=='-')sign=-1; for(n=0;dight(chr);chr=getchar())n=n*10+chr-'0';n*=sign;} void Read(ll &n){char chr=getchar(),sign=1;for(;!dight(chr);chr=getchar())if (chr=='-')sign=-1; for(n=0;dight(chr);chr=getchar())n=n*10+chr-'0';n*=sign;} int n,a[maxn],b[maxn]; ll c[maxn],s[maxn]; void hasharray(){ memcpy(b,a,n*sizeof(a[0])); sort(b,b+n); for(int i = 0;i < n;++i) a[i] = (int)(lower_bound(b,b+n,a[i]) - b) + 1; } int lowbit(int x){return x & (-x);} void update(int x,ll v){ while(x <= n){ s[x] += v; x += lowbit(x); } } ll query(int x){ ll ans = 0; while(x){ ans += s[x]; x -= lowbit(x); } return ans; } int main() { freopen("a.in","r",stdin); freopen("b.out","w",stdout); Read(n); ri i; repne(0,n,i) Read(a[i]); hasharray(); update(a[n-1],1); repde(n-2,0,i) c[i] = query(a[i]-1),update(a[i],1); memset(s,0,sizeof(s)); update(a[n-2],c[n-2]); ll ans = 0; repde(n-3,0,i) ans += query(a[i]-1),update(a[i],c[i]); cout << ans << endl; return 0; }