Skip to content

14240: 【原4240】简单序列

题目

题目描述

author: kstarxin 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4240

简单序列

对于序列的操作往往考察一些数据结构,但也不一直如此,在这个题目里,你将得到一个序列\(\lbrace a_n\rbrace\),我们将序列中的第\(n\)个元素称为\(a_n\),我们希望对序列进行加入和删除元素的操作,我们希望你给出完成这些操作之后的结果。

输入

第一行\(s\),表示输入的序列长度
第二行\(s\)个数,表示这个序列,输入的每个数后带一个空格
第三行\(p\),表示操作数目
接下来\(p\)行,每行两个数
第一个数为\(0\)或\(1\),分别表示删除和插入,第二个数为要插入或删除的数的数值

输出

一行,完成操作后这个序列从小到大排序的序列,输出的每个数后带一个空格

数据规模

\(0 < s \leq 2000000\)
\(0 < p \leq 1000000\)
\( 0 \leq |a_n| \leq 2000000\)

样例输入

5
5 4 3 2 1
2
0 5
1 6

样例输出

1 2 3 4 6

q4x3's solution

/**
 * 桶排序
 * 一个O(n)为什么要卡常
 * 枯了TAT
 * 又知道了一大堆优化方法,真好,就是头冷
 **/
#include <iostream>
#include <stdio.h>
#define re register
#define maxm 2000233
using namespace std;

inline void read(int &x){
    x = 0;
    char ch;
    bool f = 0; 
    while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
    if (ch == '-') f = 1;
    else x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
    x = f ? -x : x;
}


bool num[4002333];

int main() {
    int s;
    int p;
    re int tmp1;
    re int tmp2;
    re int tmp;
    re int tmpp;
    re int maxi(-123456789);
    re int mini(123456789);
    read(s);
    for(re int i = 0;i < s;++ i) {
        read(tmp);
        tmpp = tmp + maxm;
        num[tmpp] = 1;
        if(tmpp > maxi) maxi = tmpp;
        if(tmpp < mini) mini = tmpp;
    }
    read(p);
    for(re int i = 0;i < p;++ i) {
        read(tmp1);
        read(tmp2);
        tmpp = tmp2 + maxm;
        if(tmp1 == 1) {
            num[tmpp] = 1;
            if(tmpp > maxi) maxi = tmpp;
            if(tmpp < mini) mini = tmpp;
        } else {
            num[tmpp] = 0;
        }
    }
    for(re int i = mini;i <= maxi;++ i) {
        if(num[i])
            printf("%d ", i - maxm);
    }
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
//barrel sort
//assume no duplicat.
//NO WA please🙏
bool barrel[4000010]  = {0};
// int barrelblock[4001] = {0};
int main() {
    int n, proc;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &proc);
        barrel[2000005 + proc] = 1;
        /* ++barrelblock[(2000005 + proc) / 1000]; */
    }
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &proc);
        if (proc) {
            scanf("%d", &proc);
            barrel[2000005 + proc] = 1;
            // ++barrelblock[(2000005 + proc) / 1000];
        } else {
            scanf("%d", &proc);
            barrel[2000005 + proc] = 0;
            // --barrelblock[(2000005 + proc) / 1000];
        }
    }
    // for (int blk = 0; blk < 4000; blk++) {
    for (int i = 1 /* blk * 1000 */; /* barrelblock[blk] && */ i < 4000010; i++) {
        if (barrel[i]) {
            printf("%d ", (i - 2000005));
            // barrelblock[blk]--;
        }
    }
    /* } */
    return 0;
}

yyong119's solution

#include <cstdio>
using namespace std;
#define MAX_AN 4000100
#define ZERO 2000005

int a[MAX_AN];
int s, p, tmp;

inline int read() {
    int p, data = 0;
    char ch = 0;
    while ((ch != '-') && ch < '0' || ch > '9') ch = getchar();
    if (ch=='-') {
        p = -1;
        ch = getchar();
    } else p = 1;
    while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();
    return data * p;
}

int main() {

    scanf("%d", &s);
    for (int i = 0; i < s; ++i) {
        // scanf("%d", &tmp);
        tmp = read();
        a[tmp + ZERO] = 1;
    }

    scanf("%d", &p);
    while (p--) {
        int op, num;
        // scanf("%d%d", &op, &num);
        op = read(); num = read();
        a[num + ZERO] = op;
    }

    for (int i = 0; i < MAX_AN; ++i)
        if (a[i])
            printf("%d ", i - ZERO);
    return 0;
}

zqy2018's solution

#include <cstdio>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
bool cnt[4000005] = {0};
void init(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++i){
        int t = read();
        cnt[t + 2000000] = true;
    }
}
void solve(){
    scanf("%d", &m);
    for (int i = 0; i < m; ++i){
        int opt = read(), x = read();
        if (opt) cnt[x + 2000000] = true;
        else cnt[x + 2000000] = false;
    }
    for (int i = 0; i <= 4000000; ++i)
        if (cnt[i])
            printf("%d ", i - 2000000);
}
int main(){
    init();
    solve();
    return 0;
}