一道很经典的线段树

#include<iostream>
#include<algorithm>
#include<vector>
#define lc p<<1
#define rc p<<1|1
#define ll long long 
#define N 100005
using namespace std;

struct node
{
    ll l,r,sum;
}tr[N*4];

void PushUp(ll p)
{
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

void Update(ll p,ll x)
{
    if(tr[p].l==x&&tr[p].r==x)
    {
        tr[p].sum++;
        return;
    }
    ll m=(tr[p].l+tr[p].r)>>1;
    if(x<=m) Update(lc,x);
    if(x>m) Update(rc,x);
    PushUp(p);
}

ll Query(ll p,ll x,ll y)
{
    if(x<=tr[p].l&&tr[p].r<=y)
        return tr[p].sum;
    ll m=(tr[p].l+tr[p].r)>>1;
    ll res=0;
    if(x<=m) res+=Query(lc,x,y);
    if(y>m) res+=Query(rc,x,y);
    return res;
}

void Build(ll p,ll l,ll r)
{
    tr[p]={l,r,0};
    if(l==r) return ;
    ll m=(l+r)>>1;
    Build(lc,l,m);
    Build(rc,m+1,r);
    PushUp(p);
}

int GetLen(vector<int>arr,vector<int>brr,int n)
{
    int k=1;
    for(int i=2;i<=n;i++)
        if(arr[i]!=arr[k])
           brr[++k]=arr[i];
    brr.resize(k+1);
    return k; //K就是长度
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> arr(n+1);
    vector<int> brr(n+1);
    arr.push_back(-114514);
    for(int i=1;i<=n;i++) 
    {
        cin>>arr[i];
        brr[i]=arr[i];
    }
    sort(brr.begin(),brr.end());
    int m=GetLen(arr,brr,n);
    Build(1,1,m);
    ll res=0;
    for(int i=1;i<=n;i++) 
    {
        int ele=lower_bound(brr.begin(),brr.end(),arr[i])-brr.begin();  //一定要注意去重后要resize，以此来保证二分的正确性
        Update(1, ele);
        if (ele<m) res+=Query(1,ele+1,m);   
    }
    cout<<res<<"\n";
    return 0;
}

首先离散化，然后每趟循环维护当前元素的出现次数， (tr[p].sum++;) ,然后查询当前元素右边区间到结尾的所有元素出现次数，将这些次数累加起来就是答案。

（tips：原理就是“线段树中右区间的元素大于左区间”，如果发现右区间有元素的出现次数不是0，就表示那些元素出现的比当前元素早，而且还比当前元素大！！！ 而这就正好是逆序对的定义，即“先出现的元素大于后出现的”，所以用循环依次更新并查找次数累加起来就可以得到答案。）