与顺序相关的 \(n\) 元组求值问题，往往利用线段树进行维护，算一种经典的操作。
我们不妨先从一道简单的问题入手：求数列逆序对数。
树状数组是一个不错的选择，利用其前缀和性质维护桶，倒着扫，边扫边加数，同时查询，非排列再离散化一下，问题在 \(\Theta(n\log(n))\) 复杂度内得解。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],ans(0);
int t[N];
namespace BIT{
int lowbit(int x){return x&(-x);}
void add(int x){for(;x<=n;x+=lowbit(x)) t[x]++;}
int Qry(int x){
int res(0);
for(;x>0;x-=lowbit(x)) res+=t[x];
return res;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=n;i;i--){
ans+=BIT::Qry(a[i]);
BIT::add(a[i]);
}
printf("%d\n",ans);
return 0;
}
现在我们将问题扩展一下：对于数列中每个二元组 \((i,j)\)，满足 \(i<j\)，现在我们最大化 \(a_i-a_j\)，一样的思路，找逆序对以最大化价值，但 \(\Theta(n^2)\) 维护最大逆序对