题目链接：点击打开链接

题意是求 i a[j]>a[k] 的对数

如果只有2元组那就是求逆序数的做法

三元组的话就用一个树状数组x表示 数字i前面有多少个比自己大的个数

然后每次给这个y数组求和，再把x中>a[i]的个数存入y中即可

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include
         
           using namespace std; #define ll long long inline void rd(int &ret) { char c; do { c = getchar(); } while(c < '0' || c > '9'); ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); } #define N 1000005 #define eps 1e-8 #define inf 1000000 ll n; struct node{ ll c[N]; inline ll lowbit(ll x){return x&-x;} void init(){memset(c, 0, sizeof c);} ll sum(ll x){ ll ans = 0; while(x<=n+10) ans += c[x], x+=lowbit(x); return ans; } void change(ll x, ll y){ while(x) c[x] +=y, x-=lowbit(x); } }x, y; int haifei[1000000], panting[1000000]; int main() { ll i, j; while(cin>>n) { ll ans = 0; for(i = 0; i < n; i++)rd(haifei[i]), panting[i] = haifei[i]; x.init(); y.init(); sort(haifei, haifei+n); for(i = 0; i < n; i++) { ll b = (lower_bound(haifei, haifei+n, panting[i]) - haifei) +1; ll siz = y.sum(b); ans += siz; y.change(b, x.sum(b)); x.change(b, 1); } cout<