F - Jealous Two

题目描述：

问满足A[i] >= A[j] B[i] <= B[j]， 1 <= i, j <= n条件的 (i, j)有多少对

思路：

二维偏序

以 B[i] < B[j]作为第一关键字排序， A[i] > A[j]作为第二关键字排序，这样就消除了 B数组的限制，现在就将问题转换成求满足 ，A[i] >= A[j] ，(1 <= i <= j <= n)的条件的 (i, j)的数量，这样就类似于求逆序对，不过需要计算相同元素产生的贡献，解决这个问题只需要将求逆序对的排序的第二个关键字改反一下就行，其他的不用变

此外，这个题 i 可以等于j，所以需要先插再查，而且查找的时候不是查tr[i] - 1，而是查tr[i]，这样才能计算进去i=j的情况

而且对于 且A[i] == A[j] 且 B[i] == B[j]的情况，i和 j可以互换，要计算他们产生的贡献，计算的方法是开一个map<pair<int, int>, int>，存所有的对，再挨个计算贡献

剩下的就和求逆序对差不多了，离散化 + 树状数组

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
struct ran{
    int a, b;
    bool operator <(const ran &x)const{
        if(b != x.b)return b < x.b;
        else return a > x.a;
    }
}tr[MAX];
struct ranran{
    int val, id;
    bool operator <(const ranran &x)const {
        if(val != x.val)return val > x.val;
        else return id < x.id;
    }
}ar[MAX];

int sum[MAX];
inline int lowbit(int x){
    return x & (-x);
}
inline void insert(int i, int c){
    while (i <= 2 * n) {
        sum[i] += c;
        i += lowbit(i);
    }
}
inline int getans(int i){
    int ans = 0;
    while (i) {
        ans += sum[i];
        i -= lowbit(i);
    }
    return ans;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i].a;
    for(int i = 1; i <= n; ++i)cin >> tr[i].b;
    sort(tr + 1, tr + 1 + n);
    map<pii, int>mp;
    for(int i = 1; i <= n; ++i){
        ++mp[m_p(tr[i].a, tr[i].b)];
        ar[i].val = tr[i].a;
        ar[i].id = i;
    }
    sort(ar + 1, ar + 1 + n);
    ll ans = 0;
    for(auto [a, b] : mp){
        ans += 1ll * b * (b - 1) / 2;
    }
    for(int i = 1; i <= n; ++i){
        insert(ar[i].id, 1);
        ans += getans(ar[i].id);
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}