【二维偏序】CF Edu10 D

た入场券 2024-03-25 00:23 79阅读 0赞

[Problem - D - Codeforces][]

题意：

![82089806795f4cee9e44885cc204deb8.png][]

思路：

![c8144ab712b24fb79842a5474b9fd085.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define lowbit(x) (x & (-x))
    
    using i64 = long long;
    
    constexpr int N = 2e6 + 10;
    constexpr int M = 2e6 + 10;
    constexpr int P = 2e6;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    struct ty {
        int l, r, id;
    }a[N];
    
    int n;
    int tr[N << 1], ans[N];
    
    void add(int x, int k) {
        for (int i = x; i < N; i += lowbit(i)) tr[i] += k;
    }
    int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
    bool cmp(ty x, ty y) {
        if (x.r == y.r) return x.l < y.l;
        return x.r < y.r;
    }
    void solve() {
        std::cin >> n;
    
        std::vector<int> V;
        for (int i = 1; i <= n; i ++) {
            int l, r;
            std::cin >> l >> r;
            a[i] = {l, r, i};
            V.push_back(l);
            V.push_back(r);
        }
    
        std::sort(V.begin(), V.end());
        V.erase(std::unique(V.begin(), V.end()), V.end());
    
        for (int i = 1; i <= n; i ++) {
            a[i].l = std::lower_bound(V.begin(), V.end(), a[i].l) - V.begin() + 1;
            a[i].r = std::lower_bound(V.begin(), V.end(), a[i].r) - V.begin() + 1;
        }
    
        std::sort(a + 1, a + 1 + n, cmp);
    
        for (int i = 1; i <= n; i ++) {
            ans[a[i].id] = i - 1 - sum(a[i].l - 1);
            add(a[i].l, 1);
        }
    
        for (int i = 1; i <= n; i ++) {
            std::cout << ans[i] << '\n';
        }
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/652/problem/D
[82089806795f4cee9e44885cc204deb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/34be4f8bfd6b4143a4bf12cb9cd9d353.png
[c8144ab712b24fb79842a5474b9fd085.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/7544180acfc1469a83d92419742cb853.png