【牛客小白月赛22】NC202474 操作序列

这是一道挺不错的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！