AT_abc344_e

Kingna · 2024-03-10 17:17:01 · 题解

问题陈述

给你一个长度为 N 的序列 A=(A_1,\ldots,A_N)。A 中的元素是不同的。

请按照给出的顺序处理 Q 个查询。每个查询属于以下两种类型之一：

1 x y：在 A 中元素 x 后面紧接着插入 y。当给出此查询时，保证 x 存在于 A 中。
2 x：从 A 中删除元素 x。当给出此查询时，保证 x 存在于 A 中。

保证在处理完每一个查询后，A 都不是空的，并且其元素都是不同的。

处理完所有查询后，打印 A。

思路

这道题为什么可以用链表做呢？因为这道题只需要最后输出整个序列，而不是实时查询。题目保证 A 中的元素是不同的，这也是可以用链表的核心。

所以链表写扩展性极低，所以比赛时写的分块。为什么某某部分人都写链表呢？不言而喻。但是又想到有个 rope 的玩意，于是很开心的写出了以下代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include <ext/rope>
using namespace __gnu_cxx;
using namespace std;

const int N = 4e5 + 5;

int n, a[N];
rope<int> b;

signed main() {
    scanf("%d", &n); 
    b.push_back(0);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b.push_back(a[i]);
    }
    int q;
    scanf("%d",&q);
    while (q--) {
        int op, x, y;
        scanf("%d%d",&op,&x);
        if (op == 1) {
            scanf("%d",&y);
            b.insert(b.find(x)+1, y);
        }
        else {
            b.erase(b.find(x), 1);
        }
    }
    int t = b.size();
    for (int i = 1; i < t; i++) printf("%d ", b.at(i));
}

这份代码只过了 10 个点，不知道是 rope 的 find 函数是 O(n) 的，还是常数太大。

于是又去写分块了。

而分块思路简单，代码好调好写，清晰明了，常数小，大部分链表代码跑不过分块。

考虑把序列分成 \sqrt n 块，每块用一个 vector 动态维护，即把这个块的所有数都放到对应的 vector 里面。在某个元素后面插入一个数时，只需要在这个元素的对应块的 vector 中插入，由于每块的 vector 大小只有 \sqrt n，所以插入的时间复杂度只有 O(\sqrt n)。删除一个数也是同样的道理。

但是，真的能保证每个 vector 都是 \sqrt n 的大小吗？如果我们在固定一个位置加进很多个数，可能对应 vector 的大小就达到了 O(n) 级别。所以我们考虑块重构。即对整个序列重新分组，使得所有 vector 的大小变平均。

什么时候可以块重构？块重构是需要消耗 O(n) 的时间的，显然不能加一个数重构一次，可以间隔 \sqrt n 次重构一次，块重构复杂度 O(n\sqrt n)。

总的时间复杂度也是 O(n\sqrt n)，事实上，vector 的 insert 非常快，所以不比链表慢多少。

注意事项：

题目不是在某个位置后面添加一个数，而是在某个元素后面添加一个数，所以需要开一个数组 bel_x 代表 x 在序列的第几个块内。
本题值域较大，用 bel 数组需要离散化！用 map 复杂度就会变成 O(n\sqrt n\log n)，会 TLE！

// 394ms
#include <bits/stdc++.h>
using namespace std;

const int N = 6e5 + 5, M = 2000;

int n, q, a[N], lx[N], rx[N], len, b[N], tot;
int tmp[N], tl, sum[M], bel[N];
vector<int> bk[M];
// bk_i 存储这个块内的数
// lx_i,rx_i存储这个块的左右端点
// bel存储这个数所在的块 

struct edge {
    int op, l, r;
}ed[N]; 

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[++tot] = a[i];
    int sq = sqrt(n);
    len = n / sq;
    for (int i = 1; i <= n / sq; i++) lx[i] = (i - 1) * sq + 1, rx[i] = lx[i] + sq - 1;
    if (n % sq) {
        len++;
        lx[len] = rx[len - 1] + 1;
        rx[len] = n;
    }
    int cnt = 0;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d", &ed[i].op);
        if (ed[i].op == 1) scanf("%d%d", &ed[i].l, &ed[i].r), b[++tot] = ed[i].l, b[++tot] = ed[i].r;
        else scanf("%d", &ed[i].l); 
    }
    sort(b + 1, b + tot + 1);
    tot = unique(b + 1, b + tot + 1) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
    for (int i = 1; i <= q; i++) {
        if (ed[i].op == 1) ed[i].r = lower_bound(b + 1, b + tot + 1, ed[i].r) - b;
        ed[i].l = lower_bound(b + 1, b + tot + 1, ed[i].l) - b; 
    }
    for (int i = 1; i <= len; i++) {
        for (int j = lx[i]; j <= rx[i]; j++) bk[i].push_back(a[j]), bel[a[j]] = i; 
    }
    for (int cas = 1; cas <= q; cas++) {
        int op = 0, l = 0, r = 0;
        op = ed[cas].op;
        cnt++;
        if (op == 1) {
            l = ed[cas].l, r = ed[cas].r;
            int L = bel[l], lenb = bk[L].size(); // L是l所在的块 
            for (int i = 0; i < lenb; i++) {
                if (bk[L][i] == l) {
                    l = i; // 扫描到l的位置 
                    break;
                }
            }
            if (l == lenb - 1) bk[L].push_back(r);
            else bk[L].insert(bk[L].begin() + l + 1, r);  
            bel[r] = L;
            rx[L]++;
            for (int i = L + 1; i <= len; i++) lx[i]++, rx[i]++;
        }
        if (op == 2) {
            l = ed[cas].l;
            int L = bel[l], lenb = bk[L].size();
            for (int i = 0; i < lenb; i++) {
                if (bk[L][i] == l) {
                    l = i;
                    break;
                }
            }
            bel[bk[L][l]] = 0;
            bk[L].erase(bk[L].begin() + l);
            rx[L]--;
            for (int i = L + 1; i <= len; i++) lx[i]--, rx[i]--;
        }
        if (cnt >= 5 * sq) { // 一定次数后块重构 
            tl = 0;
            for (int i = 1; i <= len; i++) {
                for (auto j : bk[i]) tmp[++tl] = j;
            }
            sq = sqrt(tl);
            len = tl / sq;
            for (int i = 1; i <= tl / sq; i++) {
                lx[i] = (i - 1) * sq + 1, rx[i] = lx[i] + sq - 1; 
            }
            if (tl % sq) {
                len++;
                lx[len] = rx[len - 1] + 1;
                rx[len] = tl;
            }
            for (int i = 1; i <= len; i++) {
                bk[i].clear();
                for (int j = lx[i]; j <= rx[i]; j++) bk[i].push_back(tmp[j]), bel[tmp[j]] = i; 
            }
            cnt = 0;
        }
    }
    for (int i = 1; i <= len; i++) {
        if (bk[i].size() == 0) continue;    
        for (auto v : bk[i]) printf("%d ", b[v]);
    }
}