MEX and Increments

要知道，我们要想求出当前序列（i）的mex，需要有从0~i-1的所有数字，同时，将所有数字i自增1即可。记录上得到0~i-1每一个数至少一个所需要的操作数记作dp[i-1]，同时加上数字i出现的次数，就是答案了。
而在已经有0~i-1的基础上，如何得到i呢？（这就是本题的关键，即所谓的动态转移方程）：

1. i本来就存在，这种情况最简单，此时dp[i]与dp[i-1]相等。
2. i不存在，需要借助0~i-1中的数生成（注意，用来生成i的数至少出现过2次，否则0~i-1每一个数至少出现一次的条件被打破）。

为了节省时间，我们首先需要得到每一个数字出现次数的数组times[]，从times[1]开始分析，遇见大于2的数，需要将其入栈，同时记录下其出现次数（可以用pair记录，为了方便之后生成不存在的数，届时只需取出栈顶数，令其出现次数减一即可。）

#include <iostream>
#include <stack>
using namespace std;

const int N = 2e5 + 1 ;
int all[N] ;
typedef pair<int ,int> PII ;

int main(){
 int t;
 cin >>t ;
	while(t--) {
		int  n ;
		cin>>n;
		map<long long, long long> p ;
		for(int i = 0 ; i < n; i ++ ) cin>>all[i] , p[all[i]] ++ ;
		long long  sum = 0 , ch = 0 ;
		if(!p[0]) {
			cout<<"0 " ;
			for(int i = 1 ; i <= n ; i ++ ) {
				cout<<-1 <<" " ;
			}
			cout<<endl;
			continue ;
		}
		int ok = 1 ;
		cout<<p[0] <<" " ;
		p[0] -- ;
		priority_queue<PII> q;
		if(p[0] != 0) q.push({0 , p[0]}) ;

		for(int i = 1 ; i <= n;i ++ ) {
			if(ok == 0) cout<<"-1 " ;
			else if(p[i] == 0 ) {
				cout<< ch <<" " ;
				if(q.size() != 0 ){
					auto t = q.top() ;
					q.pop();
					long long x = t.first , y =t.second;
					ch += i - x ;
					y -- ;
					if(y != 0 ) {
						q.push({x , y }) ;
					}
				}
				else {
					ok = 0 ;

				}
			}
			else {
				cout<<ch + p[i] <<" " ;
				p[i] -- ;
				if(p[i]){
					q.push({i , p[i]}) ;
				}
			}

		}
		cout <<endl;
	}
	return 0 ;
}