题解：AT_abc260_d [ABC260D] Draw Your Cards

· · 题解

题目大意：模拟 n 个牌堆，每次有一次插入，先找到第一个堆顶大于等于 p_i 的堆，放到顶部。要是堆大小为 k 就处理掉这个牌堆，并把这个堆里全部数都标上 i，最后就把标记输出，要是没有处理过这张牌就输出 -1。

首先想到用 set 模拟多个牌堆的堆顶，这个数据结构有自动排序，就可以使用内置的二分函数找到对应的牌堆。这里有一个问题，这个数据结构是自动去重的，但是由于题目已经告诉我们牌上的数是一个排列，就算有去重也不会使用。

接下来如何处理牌堆内部呢？我们可以把这题看做多个单项链表，只要长度超了就用链表一个一个删除并标记。手写的链表比较复杂，可以使用一个数组 ld 表示这个牌下面的一张牌，要是位于最底部就为 0，还可以方便删除循环的终止。

之后，直接模拟即可。

先找到可以放置的牌堆地址（内置函数的默认返回值）存入 fd 中。要是 fd 为 set 的尾部，即没有找到，就得新开一个牌堆了。再使用一个数组 sz 记录牌堆大小，大小等于下面的牌的大小之和加 1。要是是新开的牌堆就默认为一张牌，即 sz_{p_i}=1。接下来的就是模拟链表操作了，新牌堆不用处理。把 ld_{p_i} 设置为 fd 对应的值，即在链表的头插入 p_i。还要注意由于牌堆堆顶的更改，要删除 fd。接着，无论如何操作都会放牌，直接把牌加入 set 内即可。再是删除，首先是删堆顶，要在 set 内处理，接着就是一张一张删除标记了，具体见代码。完成这一串操作后，直接输出答案即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,p[N],ld[N],sz[N],et[N];
set<int>st;
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){cin>>p[i];}
    for(int i=1;i<=n;i++){
        auto fd=st.upper_bound(p[i]);
        if(fd==st.end()){
            sz[p[i]]=1;
        }else{
            sz[p[i]]=sz[*fd]+1;
            ld[p[i]]=*fd;
            st.erase(fd);
        }
        st.insert(p[i]);
        if(sz[p[i]]==k){
            st.erase(p[i]);
            for(int er=p[i];er;er=ld[er])et[er]=i;
        }
    }
    for(int i=1;i<=n;i++){
        if(et[i]==0)cout<<-1<<'\n';
        else cout<<et[i]<<'\n';
    }
    return 0;
}