这是一道挺不错的STL模拟题,做法也很多,可以借此巩固一下对STL的知识运用

由于数列长度无限,所以我们需要离散化,可以用一个容器(如map,set,建议先了解一下它们的用法及基本的指针用法)存储不为0的数及它的下标

  • 增加操作:给下标为 tt 的数加 cc 。特别注意,如果在下标 [t-30,t+30] 内有不为零的数,增加操作无效。
    【对于下标 [t-30,t+30] 内,可以直接枚举扫一遍,还可以用lower_bound查询下标>=t-30的第一个数,然后判断它的下标是否<=t+30】

  • 削减操作:让数列中下标最小的不为零数变为零。
    【如果容器中有数变为0了,我们就直接erase把它去除,让容器中只存储不为0的数,这样数列中下标最小的不为零数就是容器中的第一个数了,用begin即可操作】

  • 查询操作:查询数列中下标为 tt 的数字是多少。
    【分两种情况,下标tt上可能没有数字,即为0,不在我们的容器当中,所以我们首先要用lower_bound或(map)count来查询这个数是否在容器中再输出】

对于每个操作,可能是一个数也可能是两个数,其实我们不用字符串读入,不管用什么容器都可以用下面的模板

#include<cstdio>
using namespace std;
map<int,int> a;
int main(){
    int n;
    scanf("%d",&n);
    for (int t,c;n;n--){
        scanf("%d",&t);//先读入第一个数
        if (getchar()=='\n'){//下一个字符是换行符吗?(如果有第二个数则getchar()读入的是空格,如果是换行符说明只有一个数)
            if (t==-1){
               //削减操作
            }
            else {
               //查询操作
            }
        }else{
           //增加操作
        }
    }
}

小提示:

  • auto可以自动推导变量类型,编译器根据初始化表达式(根据“=”右侧的变量类型)来自动推导变量类型,在代码中代替迭代器类型写起来比较简便,不过有些C++上可能用不了(牛客上的C++可以)
  • lower_bound(val)返回大于或等于val的第一个元素位置。如果查询不到,则返回end()

方法一:map

#include<cstdio>
#include<map>
using namespace std;
map<int,int> a;//二元组分别是坐标和对应的数
int main(){
    int n;
    scanf("%d",&n);
    for (int t,c;n;n--){
        scanf("%d",&t);
        if (getchar()=='\n'){
            if (t==-1){
                if (a.empty()) puts("skipped");//没有不为0的数了
                else printf("%d\n",a.begin()->second),a.erase(a.begin());//输出第一个二元组存储的数并把它删去(变为0)
            }
            else {
                if (a.count(t)) printf("%d\n",a[t]);//count查询是否有坐标为t
                else puts("0");
            }
        }else{
            scanf("%d",&c);
            auto pos=a.lower_bound(t-30);//这里的auto相当于map<int,int>::iterator
            if (pos==a.end() || pos->first>t+30) a[t]=c;//如果[t-30,t+30]没有不为0的数
        }
    }
}

方法二:set

#include<cstdio>
#include<set>
using namespace std;
set<pair<int,int> > a;
pair<int,int> tmp;
int main(){
    int n;
    scanf("%d",&n);
    for (int t,c;n;n--){
        scanf("%d",&t);
        if (getchar()=='\n'){
            if (t==-1){
                if (a.empty()) puts("skipped");//没有不为0的数了
                else {
                    printf("%d\n",(*a.begin()).second);//输出第一个二元组存储的数
                    a.erase(a.begin());//把它删去(变为0)
                }
            }
            else {
                tmp.first=t;
                auto pos=a.lower_bound(tmp);//查询是否有二元组坐标为t,这里的auto相当于set<pair<int,int> >::iterator
                if(pos==a.end() || (*pos).first!=t) puts("0");
                else printf("%d\n",(*pos).second);
            }
        }else{
            scanf("%d",&c);
            tmp.first=t-30;
            auto pos=a.lower_bound(tmp);//这里的auto相当于set<pair<int,int> >::iterator
            if(pos==a.end() || (*pos).first>t+30) a.insert(make_pair(t,c));//如果[t-30,t+30]没有不为0的数,则在容器中加入新数字及下标
        }
    }
}

方法三:据出题者说除此之外还“可以离线下来胡搞,也可以平衡树在线”,由于作者能力有限,就留给dalao去探索吧qwq

如果题解中有什么错误或可以改进的地方,还望大家在评论区指出qwq!