hey_left 2 Codeforces Round 918 (Div. 4) 续

题目链接

F.

常规的树状数组求逆序对
需要注意的是，因为是下标与值的映射，所以数值不能为负数，也不能太大
然后传参数的时候，参数是最大数值
切记切记

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10;

template <typename T>
struct TreeArray{
    vector<T> tree;

    TreeArray(T n){
        tree.resize(n+1,T(0));
    }

    void update(T index,T value){
        while(index<tree.size()){
            tree[index]+=value;
            index+=index&(-index);
        }
    }

    T query(T index){
        T sum=0;
        while(index>0){
            sum+=tree[index];
            index-=index&(-index);
        }
        return sum;
    }
};


void solve(){
    int n;cin>>n;
    pair<int,int>a[N];
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+1+n);
//    for(int i=1;i<=n;i++){
//        cout<<a[i].first<<' '<<a[i].second<<endl;
//    }
    TreeArray<int>ta(100000);
    int sum=0;
    for(int i=1;i<=n;i++){
        ta.update(a[i].second,1);
        //cout<<i<<' '<<ta.query(a[i].second)<<endl;
        sum+=max(0,i-ta.query(a[i].second));
    }
    cout<<sum<<'\n';
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int hey_left=1;
    //cin>>hey_left;
    while(hey_left--){
        solve();
    }
    return 0;
}

虽然但是，这道题还是没有解决
因为数据有负数且很大
要进行离散,再用普通树状数组

举一个简单的例子：
1 2 3
1 2 100
它们的逆序对数是一样的
也就是说我们不一定要记录真实的数值，数字间只要满足同样的相对大小即可
一列数字 1 3 2
记录下输入顺序 1 2 3
然后按升序排序 1 2 3
对应的原输入顺序 1 3 2
排好序的数 值映射到1-n
但我们的输入顺序是不变的
所以再开一个数组c，然后便利序列 ，c[输入顺序]=i
具体看代码吧，表达能力有限
得到的b数组就可以用普通树状数组做了

给出离散部分的代码：

pair<int,int>b[N];
bool cmp(pair<int,int>x,pair<int,int>y){//一维是数值，二维是输入顺序
    if(x.first!=y.first)return x.first<y.first;
    else return x.second<y.second;//就是说排序时有相同的数值，那么就按输入顺序排
}
for(int i=1;i<=n;i++){
        cin>>b[i].first;
        b[i].second=i;
}
sort(b+1,b+1+n,cmp);
int c[N];
    for(int i=1;i<=n;i++){
        c[b[i].second]=i;
    }

至此，终于过了
感觉归并排序就没有这个问题，但对递归有天然的恐惧，就用这个吧

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10;
#define int long long
template <typename T>
struct TreeArray{
    vector<T> tree;

    TreeArray(T n){
        tree.resize(n+1,T(0));
    }

    void update(T index,T value){
        while(index<tree.size()){
            tree[index]+=value;
            index+=index&(-index);
        }
    }

    T query(T index){
        T sum=0;
        while(index>0){
            sum+=tree[index];
            index-=index&(-index);
        }
        return sum;
    }
};
bool cmp(pair<int,int>x,pair<int,int>y){
    if(x.first!=y.first)return x.first<y.first;
    else return x.second<y.second;
}
pair<int,int>b[N];
void solve(){
    int n;cin>>n;
    pair<int,int>a[N];
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        cin>>b[i].first;
        b[i].second=i;
    }
    sort(b+1,b+1+n,cmp);
    int c[N];
    for(int i=1;i<=n;i++){
        c[b[i].second]=i;
    }
    TreeArray<int>ta(n);
    int sum=0;
    for(int i=1;i<=n;i++){
        ta.update(c[i],1);
        //cout<<i<<' '<<ta.query(a[i].second)<<endl;
        sum+=max(0ll,i-ta.query(c[i]));
    }
    cout<<sum<<'\n';
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int hey_left=1;
    cin>>hey_left;
    while(hey_left--){
        solve();
    }
    return 0;
}