题解 | 小红的慕斯模具统计

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

int main()
{
    int N, X, K;
    cin >> N >> X >> K;
    vector<int> Q(K, 0);
    const int mxn = 1e5 + 5;
    for (int i = 0; i < K; i++)
    {
        cin >> Q[i];
    }

    int M;
    cin >> M;
    unordered_map<int, unordered_set<int>> mp;
    for (int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        mp[y].insert(x);
    }
    // 离线滑动窗口
    vector<int> ans(mxn, 0);
    unordered_set<int> cur;
    unordered_map<int, int> cnt;
    for (int i = 0; i < X; i++)
    {
        auto temp = mp[i];
        for (auto x : temp)
        {
            cur.insert(x);
            cnt[x]++;
        }
    }
    ans[0] = cur.size();

    for (int l = 1; l < mxn; l++)
    {
        auto temp = mp[l - 1];
        for (auto x : temp)
        {
            if (cnt[x] == 1)
            {
                cur.erase(x);
            }
            cnt[x]--;
        }
        int right = l + X - 1;
        auto r = mp[right];
        for (auto x : r)
        {
            cnt[x]++;
            cur.insert(x);
        }
        ans[l] = cur.size();
    }
    for (int i = 0; i < K; i++)
    {
        cout << ans[Q[i]] << " ";
    }
    system("pause");
}