Problem
题目大意：
有一个空集，要求支持以下两个操作：
- 插入一个数 (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
",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;
}