Codeforces Round #615 (Div. 3)D. MEX maximizing

题目链接：https://codeforces.com/contest/1294/problem/D

题意：

给你 q 个询问和 一个 x ， 每次询问输入一个数 n ，你可以把它减任意次 x 或 加任意次 x，然后添入数组，问每次询问结束时数组里最小的没出现的非负整数是多少

其实这里面的MEX函数是博弈论中sg函数的一个重要组成部分，MEX函数定义为数组里最小的没出现的非负整数

乍一看其实非常不好下手，但是条件中的任意加任意减x我们可以理解为每个数其实都具有一定的特征，我指的是ai%x，对于ai%x相同的数其实是没有差别的，因为你无限次加减嘛都一样的，所以我们就可以把每个数都压缩在[0,x-1]区间内，那我们如何检验数组里最小的没出现的非负整数呢，一个个找嘛，不会超时吗？不 我们是记忆化上一次的答案接着找，所以不会超时，只要看ans%x是不是有存在即可，但是要消耗一个ai%x，这句话需要好好理解下

其实这种题目一开始都是很难想的，感觉具体实现会非常繁琐，但是一般都要找到其不变的本质，想这道题目就是把每次需要检验的数映射到一个区间内的数，看看它存不存在，完美的利用了可以任意加任意减这个性质，我对这道题的理解大概是这样，如有不足不吝赐教

#include<bits/stdc++.h>
#define ll long long
#define rg register ll
using namespace std;
ll q,x,ans,p[400005];
int main()
{
    cin>>q>>x;
    for(rg i=1;i<=q;i++)
    {
        ll val;
        cin>>val;
        p[val%x]++;
        while(p[ans%x])p[ans%x]--,ans++;
        cout<<ans<<endl;
    }
    while(1)getchar();
    return 0;
}