Submission #74603814

---

Source Code Expand

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

using ll = long long;

// Fenwick Tree (BIT)
struct BIT {
    int n;
    vector<int> bit;
    BIT(int n_) : n(n_), bit(n_ + 2, 0) {}
    void add(int idx, int delta) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] += delta;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res += bit[idx];
        return res;
    }
    int range_sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q, K;
    cin >> N >> M >> Q >> K;

    vector<pair<int, int>> books(M); // (pages, shelf)
    for (int i = 0; i < M; i++) {
        int s, d;
        cin >> s >> d;
        books[i] = {d, s};
    }

    // 查询: (T, L, R, index)
    struct Query {
        int T, L, R, idx;
    };
    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++) {
        int l, r, t;
        cin >> l >> r >> t;
        queries[i] = {t, l, r, i};
    }

    // 按页数降序排序
    sort(books.begin(), books.end(), greater<pair<int, int>>());
    // 按 T 降序排序
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.T > b.T;
    });

    BIT bit(N);
    vector<int> ans(Q);

    int book_idx = 0;
    for (const auto& q : queries) {
        while (book_idx < M && books[book_idx].first >= q.T) {
            bit.add(books[book_idx].second, 1);
            book_idx++;
        }
        int cnt = bit.range_sum(q.L, q.R);
        ans[q.idx] = max(cnt - K, 0);
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

Submission Info

Judge Result