空间最小

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

const int MAXN = 200010;  // 根据题目范围确定

int main() {
    int n, k, q;
    cin >> n >> k >> q;
    
    // 只需要两个数组：差分数组合并前缀和计算
    int d[MAXN + 5] = {0};  // 差分数组
    
    // 读取区间并构建差分数组
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        d[l]++;
        d[r + 1]--;
    }
    
    // 直接在差分数组上计算前缀和，并用它存储最终的前缀和结果
    int cnt = 0;
    for (int i = 1; i < MAXN; i++) {
        cnt += d[i];
        // 复用d数组存储前缀和
        d[i] = d[i - 1] + (cnt >= k ? 1 : 0);
    }
    
    // 回答查询
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << d[r] - d[l - 1] << "\n";
    }
    
    return 0;
}