题解：P7549 [BJWC2017] 神秘物质

Bb1t · 2024-04-12 15:54:22 · 题解

Solution

容易发现 max 就是区间的极差，min 就是相邻两数之差的最小值。

快速插入一个数和删除一个数容易想到链表，还要支持区间的询问，考虑块状链表。其实是不会平衡树

设阈值为 B。

块状链表其实就是外部结构是链表，里面是顺序表（可以用 vector<int> 实现）。我们让里面顺序表大小为 O(B)，这样插入删除定位需要 O(B + \dfrac{n}{B})。

但大小会随着插入删除变化，有可能不再是 O(B) 的大小了，这时候合并分裂就行了（其实合并可以不做）。

为了能够快速回答询问，每个块里需要维护额外信息。本题中需要维护最大值，最小值以及相邻之差的最小值。

具体来讲，回答询问时先在链表上跳定位，两边的散块暴力扫，之后暴力扫每个块，对于 min 询问，记得处理块与块之间相邻的数。该段时间复杂度 O(B + \dfrac{n}{B})。

取 B=\sqrt n 时理论复杂度最优，我取的 B=400。

Code

其实有点恶心，需要耐心地调。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
constexpr int N = 1e5 + 5, B = 400;
int cnt = 1;
struct node {
    vector<int>v;
    int nxt, mx, mn, t;
    node() {
        nxt = 0, mx = 0, mn = INT_MAX, t = INT_MAX;
    }
    inline void init()
    {
        if (v.empty()) return;
        mx = *max_element(all(v));
        mn = *min_element(all(v));
        t = INT_MAX;
        for (int i = 1; i < v.size(); ++i) {
            t = min(t, abs(v[i] - v[i - 1]));
        }
    }
    inline void push(int x)
    {
        mx = max(mx, x);
        mn = min(mn, x);
        if (!v.empty()) t = min(t, abs(x - v.back()));
        v.emplace_back(x);
    }
    inline void push(vector<int>::iterator it, int x)
    {
        mx = max(mx, x);
        mn = min(mn, x);
        v.emplace(it, x);
    }
}a[N];
int getpos(int &x)
{
    int p = 1;
    while (x > a[p].v.size()) {
        x -= a[p].v.size();
        p = a[p].nxt;
    }
    return p;
}
void work(int p)
{
    if (!a[a[p].nxt].nxt) return;
    if (a[p].v.size() + a[a[p].nxt].v.size() <= 1.5 * B) {
        for (int x : a[a[p].nxt].v) {
            a[p].push(x);
        }
        a[p].nxt = a[a[p].nxt].nxt;
    } else if (a[p].v.size() >= 1.5 * B) {
        int q = a[p].v.size() / 2;
        a[++cnt].nxt = a[p].nxt;
        a[p].nxt = cnt;
        for (int i = a[p].v.size() - q; i <= a[p].v.size() - 1; ++i) {
            a[cnt].push(a[p].v[i]);
        }
        while (q--) a[p].v.pop_back();
        a[p].init();
    }   
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (a[cnt].v.size() >= B) a[cnt].nxt = cnt + 1, ++cnt;
        a[cnt].push(x);
    }
    while (m--) {
        string op;
        int x, y;
        cin >> op >> x >> y;
        if (op == "merge") {
            int p = getpos(x);
            a[p].v[x - 1] = y;
            if (x == a[p].v.size()) {
                if (!a[p].nxt) a[p].nxt = ++cnt;
                a[a[p].nxt].v.erase(a[a[p].nxt].v.begin());
                a[a[p].nxt].init();
            } else {
                a[p].v.erase(a[p].v.begin() + x);
            }
            a[p].init();
            work(p);
        } else if (op == "insert") {
            int p = getpos(x);
            if (x == a[p].v.size()) {
                if (!a[p].nxt) a[p].nxt = ++cnt;
                a[a[p].nxt].push(a[a[p].nxt].v.begin(), y);
                a[a[p].nxt].init();
            }
            else {
                a[p].push(a[p].v.begin() + x, y);
                a[p].init();
            }
            work(p);
        } else if (op == "max") {
            int p = getpos(x), q = getpos(y), mx = 0, mn = INT_MAX;
            if (p == q) {
                for (int i = x - 1; i < y; ++i) {
                    mx = max(mx, a[p].v[i]);
                    mn = min(mn, a[p].v[i]);
                }
            } else {
                for (int i = x - 1; i < a[p].v.size(); ++i) {
                    mx = max(mx, a[p].v[i]);
                    mn = min(mn, a[p].v[i]);
                }
                for (int i = 0; i < y; ++i) {
                    mx = max(mx, a[q].v[i]);
                    mn = min(mn, a[q].v[i]);
                }
                p = a[p].nxt;
                for (int i = p; i != q; i = a[i].nxt) {
                    mx = max(mx, a[i].mx);
                    mn = min(mn, a[i].mn);
                }
            }
            cout << mx - mn << '\n';
        } else {
            int p = getpos(x), q = getpos(y), ans = INT_MAX;
            if (p == q) {
                for (int i = x; i < y; ++i) {
                    ans = min(ans, abs(a[p].v[i] - a[p].v[i - 1]));
                }
            } else {
                for (int i = x; i < a[p].v.size(); ++i) {
                    ans = min(ans, abs(a[p].v[i] - a[p].v[i - 1]));
                }
                for (int i = 1; i < y; ++i) {
                    ans = min(ans, abs(a[q].v[i] - a[q].v[i - 1]));
                }
                for (int i = p; i != q; i = a[i].nxt) {
                    ans = min(ans, abs(a[i].v.back() - *a[a[i].nxt].v.begin()));
                    if (i != p) ans = min(ans, a[i].t);
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}