题目描述

blablabla

样例

blablabla

算法1

(二分) $O(nlogn)$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;
typedef pair<int, int> pii;

int a[N];
pii p[N];
int cnt[N];
int n, k;
int ans[N];

bool cmp(pii a, pii b){
    return a.first > b.first;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        p[i] = {a[i], i};
    }
    sort(p+1, p + n + 1, cmp);
    while(k --){
        int x, y;
        cin >> x >> y;
        if(a[x] > a[y]) cnt[x] ++;
        if(a[x] < a[y]) cnt[y] ++;
    }
    for(int i=1;i<=n;i++){
        int x = p[i].first, j = p[i].second;
        int l = i, r = n;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(p[mid].first == x) l = mid;
            else r = mid - 1;
        }
        ans[j] = max(0, n - r - cnt[j]);
    }
    for(int i=1;i<=n;i++) cout << ans[i] << ' ';
    return 0;
}