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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int N,X,K; // 种类，每个跨度，数量
    cin>>N>>X>>K;
    vector<int> shijiandian(K);
    for(int i=0;i<K;i++){
        cin >> shijiandian[i];
    }
    
    int M; //数据数
    cin>>M;
    int max_jm =0; //最长时间
    vector<pair<int,int>> datas(M);//数据
    for(int i=0;i<M;i++){
        int im,jm; //编号，时间
        cin>>im>>jm;
        datas[i]={im,jm};
        if(jm>max_jm) max_jm=jm;
    }

    vector<vector<int>> time_data(max_jm+1); //时间对应数据
    for(auto &d :datas){
        time_data[d.second].push_back(d.first);
    }

    vector<int> cnt(N,0);  //cnt 滑动窗口
    int key=0;

    //初始化窗口
    int right_bound = min(X -1,max_jm);
    for(int i=0;i<=right_bound;i++){
        for(int id : time_data[i]){
            if(cnt[id]==0) key++;
            cnt[id]++;  //对应时间有数据，滑动窗口id位置标1
        }
        
    }

    vector<int> key_gather(max_jm+1,0);  //结果集合
    key_gather[0]=key;
    
    //滑动窗口向右
    for(int i=0;i<max_jm;i++){
        //移除左端点 i
        for(int id : time_data[i]){
            cnt[id]--;
            if(cnt[id]==0) key--;
        }

        //添加右端点 i+X
        int x = i+X;
        if(x<=max_jm){
            for(int id : time_data[x]){
                if(cnt[id]==0) key++;
                cnt[id]++;
            }
        }

        key_gather[i+1] = key; 
    }

    for(int i=0;i<K;i++){
        int s = shijiandian[i];
        if(s>max_jm) cout<<0<<" ";
        else cout<<key_gather[s]<<" ";
    }
    
    return 0;
}