MEX maximizing

题意

开始给一个空的数列，然后q次询问，每一次询问都会添加一个数，我们可以对当前的数列的任意非负数进行加减x，然后求出多种方案中未出现的最小非负整数中最大的是哪个。

分析

对添加的数进行对X取模，并进行记录取模后的值a，以及a出现的次数t，对于每次询问答案ans = a+x*t
t和a都是最小的，t是主键，a是次键

代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e6+10;
typedef pair<int,int> pii;
int cnt[maxn];//cnt[i]：表示取模x后等于i的次数
priority_queue<pii,vector<pii>,greater<pii> > q;

int Q,X,y;
int main(){
    cin>>Q>>X;
    for(int i = 0;i<X;i++) q.push({0,i});
    while(Q--){
        scanf("%d",&y);
        cnt[y%X]++;
        q.push({cnt[y%X],y%X});
        while(q.top().first<cnt[q.top().second]) q.pop();//对于已经修改过的记录进行跳过
        pii t = q.top();
        printf("%d\n",t.first*X+t.second);
    }
    return 0;
}