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

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

int main() {
    int N,X,K;
    cin>>N>>X>>K;

    vector<int> S(K);
    for(int i=0;i<K;++i){
        cin>>S[i];
    }

    int M;
    cin>>M;
    vector<pair<int,int>> records(M);
    for(int i=0;i<M;++i){
        cin>>records[i].second>>records[i].first;
    }
    sort(records.begin(),records.end());
    vector<int> res(K);
    unordered_map<int,int> freq;
    int current_unique=0;
    int left=0;
    int right=0;
    vector<pair<int,int>> queries(K);
    for(int i=0;i<K;i++){
        queries[i]={S[i],i};
    }
   // cout<<-1<<endl;
    sort(queries.begin(),queries.end());
    int ans[100005]={0},tip[100005]={0};
    for(int i=0;i<K;i++){
        
        int l=queries[i].first;
        int r=l+X-1;
        if(i>0) ans[queries[i].second]=ans[queries[i-1].second];
        //  cout<<-2<<" "<<l<<" "<<r<<endl;
         
        while(records[right].first<=r&&right<M){
            if(tip[records[right].second]==0)
            ans[queries[i].second]++;
            tip[records[right].second]++;
            right++;
        }
        while(records[left].first<l&&left<M){
            tip[records[left].second]--;
            if(tip[records[left].second]==0)
            ans[queries[i].second]--;
            left++;
        }
      //  cout<<ans[queries[i].second]<<" "<<queries[i].second<<" "<<left<<" "<<right<<endl;
       // for(int j=0;j<N;j++)
        //cout<<tip[j]; cout<<endl;
    }
    for(int i=0;i<K;i++){
        cout<<ans[i]<<" ";
    }
}
// 64 位输出请用 printf("%lld")