树状数组写法

#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N =  1 *1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n;
struct node
{
    LL idx,v;
}c[N];
LL tr[N],p[N];
bool cmp(node a,node b)
{
  if(a.v != b.v) return a.v < b.v;
  return a.idx < b.idx;
}
int lowbit(int x)
{
  return x & -x;
}
void add(int x,int c)
{
  for(int i=x;i<=n;i+=lowbit(i)) tr[i] += c;
}
LL sum(int x)
{
  int res = 0;
  for(int i=x;i;i-=lowbit(i)) res += tr[i];
  return res;
}
inline void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i].v;
        c[i].idx = i;
    }
    sort(c+1,c+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        p[c[i].idx] = i; //离散化
    }
    LL res = 0;
    for(int i=1;i<=n;i++)
    {
        add(p[i],1);
        res += i - sum(p[i]);
    }
    cout<<res;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    // int _; cin>>_; while(_--){}
    solve();
    return 0;
}

```


```

参考答案：

#include<iostream>

using namespace std;

const int N = 200010;
int a[N], tmp[N];

long long merge_sort(int a[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;
    long long res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
    int k = 0, i = l, j = mid + 1;

    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (int i = l, j = 0; i <= r; ++i, ++j) a[i] = tmp[j];

    return res;
}
int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    cout << merge_sort(a, 0, n - 1) << endl;

    return 0;
}