D - Draw Your Cards(模拟)

D - Draw Your Cards(模拟)

用一个set维护当前所有堆对应的堆顶数。

每次lowerbound找，如果有则用链表插到表头。开一个数组记录cnt。

如果cnt=k，则遍历更新答案，然后从set里删掉堆顶。

每个元素最多遍历一次删除一次。

#includeusing namespace std;const int N=2e5+10;int n,k,ans[N],cnt[N],to[N];sets;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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。