题解 SP27379 【BLUNIQ - Unique Code】

Mine_King · 2021-10-10 22:14:23 · 题解

在我的博客获得更好的阅读体验

Problem

SP27379 BLUNIQ - Unique Code

题目大意：

有一个空集，要求支持以下两个操作：

• 插入一个数 x，若集合中已有 x，则改为插入 x+1。若已有 x+1，则改为插入 x+2，以此类推，并返回最终插入的数。
• 删除一个数 y。

Solution

首先我们可以想到在任意时刻集合中的数的排列一定是这样的：

那么对于每个插入的数，我们只要分两种情况：

• 当前位置已经有数了：插入这段后面的一个空位（即图中的红色方框）,同时删去这个红色方框。因为这个位置已经被占用了。
• 当前位置没有数：直接插入。不会造成影响。

但是我们同时意识到，插入之后可能会出现新的红色方框。于是我们要重新维护。这时又分两种情况：

• 后面是一个空位（图一）：将这个空位变为红色方框。
• 后面是一段连续的数：啥都不用做。因为和其他的段合并了。

还有一个特例：新插入的数刚好和一个红方框重合，那么要先把这个红方框删掉。

注意到第一个操作不需要考虑前面的数的情况。

第二个操作呢？更简单了。

还是分两种情况：

• 前面没有数：直接删掉这个数。相当于是独立的一段，一段都删没了就没用了。
• 前面有数：把它变成红色方框。这个位置是一段的末尾，既然没了就变成红色方框了。

注意到第二个操作不需要考虑后面的数的情况。

那么怎么维护呢？思考一下，我们需要两个这样的数据结构，一个维护黑色段，一个维护红色方框。要求支持查询是否存在，求比它大的最小的数，这是什么？set！

Code

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
set<int>s1,s2;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)
        {
            set<int>::iterator it=s1.find(x);
            int ans;
            if(it==s1.end()) s1.insert(ans=x);//不存在
            else s1.insert(ans=*s2.lower_bound(x)),s2.erase(ans);//存在
            //插入
            printf("%d\n",ans);
            if(s2.find(ans)!=s2.end()) s2.erase(ans);//特例
            if(s1.find(ans+1)==s1.end()) s2.insert(ans+1);//后面有数
            //删红方框
        }
        else
        {
            s1.erase(x);
            if(s1.find(x-1)!=s1.end()) s2.insert(x);//前面有数
        }
    }
    return 0;
}