D - Draw Your Cards (Simulation)

D - Draw Your Cards(模拟)

用一个setMaintain the number of heap tops corresponding to all current heaps.

每次lowerbound找,If there is, insert it into the header with a linked list.开一个数组记录cnt.

如果cnt=k,Then iterate over to update the answer,然后从setdelete the top of the heap.

Each element is traversed at most once and removed once.

时间复杂度：$O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,ans[N],cnt[N],to[N];
set<int>s;
int main()
{
    
	scanf("%d%d",&n,&k);
	memset(ans,-1,sizeof(ans));
	for(int i=1,x;i<=n;i++)
	{
    
		scanf("%d",&x);
		auto it=s.lower_bound(x);
		if(it==s.end())s.insert(x),cnt[x]=1;
		else cnt[x]=cnt[*it]+1,to[x]=*it,s.erase(it),s.insert(x);
		if(cnt[x]==k)
		{
    
			for(int j=x;j;j=to[j])ans[j]=i;
			s.erase(s.find(x));
		}
	}
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}