[线段树]打字练习2

1.P1908 逆序对

动态开点线段树/离散化均可解决。

动态开点线段树维护桶，每次插值时统计值域上 [ v a l , m a x _ v a l ] [val, max\_val] [val,max_val]的区间和，比其大的数的个数就是对总逆序对个数的贡献。

#include 
#define ll long long 
using namespace std;

const int maxn = 5e5, maxx = 1e9 + 7;
int sum[maxn  n;
    ll ans = 0;
    for(int i = 1; i > x;
        ans += query(root, 1, maxx, x + 1, maxx);
        update(root, 1, maxx, x, 1);
    }
    cout