树状数组的几个基本应用（更新ing）

一、求逆序对

最好能加入离散化，离散化的方式值得学习，开一个结构体，保存输入序，之后再按值大小排序，最后按输入序赋值1-n。

#include
#define ll long long
#define rep(i,x,n) for(int i=x;i<=n;i++)
using namespace std;
const int N = 1000001;
int n,x,tr[N],b[N];
struct node{
    int v,p;
    bool operator<(const node &nxt) const{
        if(v==nxt.v) return p> n;
    rep(i,1,n)
    {
        cin >> a[i].v;
        a[i].p=i;//p是输入序，为啥有输入序呢，因为直接存储值太大了，有1e9，存不下，需要离散化，这就是离散化的关键一步
    }
    sort(a+1,a+n+1);
    rep(i,1,n) b[a[i].p]=i;//这一步就用上了
    rep(i,1,n)
    {
        ans+=sum(n)-sum(b[i]);
        add(b[i],1);
    }
    cout << ans;
}