树状数组求逆序数模板

忘是亡心i 2022-05-15 18:56 233阅读 0赞

## 以前求逆序数都是用的归并排序，现在发现树状数组求逆序数更简单，常数更小，留个板子，数值较大时需要离散化，用map实更简单，入门参考[https://www.cnblogs.com/xiongmao-cpp/p/5043340.html][https_www.cnblogs.com_xiongmao-cpp_p_5043340.html]。 ##

## 普通逆序数代码： ##

#pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    #define lb(x) (x&(-x))
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int n,x,tr[N];
    
    void upd(int x,int v) {
        for(int i=x;i<N;i+=lb(i))
            tr[i]+=v;
    }
    
    int qy(int x) {
        int res=0;
        for(int i=x;i>0;i-=lb(i))
            res+=tr[i];
        return res;
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        while(cin>>n) {
            int ans=0;
            mst(tr,0);
            for(int i=1;i<=n;i++) {
                cin>>x;
                upd(x,1);
                ans+=i-qy(x);///统计当前序列中大于a的元素的个数
            }
            cout<<ans<<endl;
        }
        return 0;
    }

# #

## 离散化逆序数代码： ##

#pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    #include<ext/pb_ds/assoc_container.hpp>
    #include<ext/pb_ds/hash_policy.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    #define lb(x) (x&(-x))
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int n,ls[N],tr[N];
    
    struct nd{
        int v,id;
        bool operator < (const nd &a) const {
            return v<a.v;
        }
    }a[N];
    
    void upd(int x) {
        for(int i=x;i<N;i+=lb(i))
            tr[i]++;
    }
    
    int gs(int x) {
        int rs=0;
        while(x>0) {
            rs+=tr[x];
            x-=lb(x);
        }
        return rs;
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].v,a[i].id=i;
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++) ls[i]=a[i].id;
        ll ans=0;
        for(int i=1;i<=n;i++) {
            ans+=i-1-gs(ls[i]);
            upd(ls[i]);
            ///等同的写法
            ///upd(ls[i]);
            ///ans+=i-gs(ls[i]);
        }
        cout<<ans<<endl;
        return 0;
    }

[https_www.cnblogs.com_xiongmao-cpp_p_5043340.html]: https://www.cnblogs.com/xiongmao-cpp/p/5043340.html