数据结构杂烩
2025-02-10

ds is fun ——@crashed


Warm up! I

多重集 / 彩虹蛋糕

http://222.180.160.110:61235/contest/6010/problem/7

好像并不是第一次见了?像是把几个二元组的同一维拿来整活,可以考虑恒等变形转化为偏序问题

\(a_{i,0}+b_{j,0}\ge a_{i,1}+b_{j,1}\),则 \(a_{i,0}-a_{i,1}\ge b_{j,1}-b_{j,0}\)。如果我们把 \(a\) 按照 \(a_{i,0}-a_{i,1}\) 排序并把 \(b\) 按照 \(b_{j,1}-b_{j,0}\) 排序,那么若需要求某个时刻的答案,需要对于每一个 \(i\),找到最小的 \(b_{j,0}\),使得 \(b_{j,1}-b_{j,0}\)\([-\infty, a_{i,0}-a_{i,1}]\) 中,同时找到最小的 \(b_{j,1}\),使得 \(b_{j,1}-b_{j,0}\)\([a_{i, 0}-a_{i,1},+\infty]\) 中。

那么有一个很神的方法(似乎也不是第一次遇到了但总结不出来 晕),我们在线段树 pushup 的时候,尝试用左边的 \(b_{j,0}\) 更新右边的答案。

牢游说之所以觉得很熟悉是因为我之前 % 你赛做到过这道题还 A 了???离谱的。

为啥 llsw 一定说是离线啊 晕 想不到什么好的离线解决时间限制的方案 晕 所以还是在线。

#include <bits/stdc++.h>
const int inf = 2e9 + 1;
struct _ { long long aa, ab, ba, bb, u; int l, r, id; };
std::vector<_> t(1);
std::vector<std::multiset<long long> > aa(1), ab(1), ba(1), bb(1);
int tot, cnt;
#define lt t[p].l
#define rt t[p].r
void pushup(int p) {
    t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
    if (lt) {
        t[p].u = t[lt].u;
        t[p].aa = t[lt].aa, t[p].ab = t[lt].ab, t[p].ba = t[lt].ba, t[p].bb = t[lt].bb;
    }
    if (rt) {
        t[p].u = std::min(t[p].u, t[rt].u);
        t[p].aa = std::min(t[p].aa, t[rt].aa), t[p].ab = std::min(t[p].ab, t[rt].ab), t[p].ba = std::min(t[p].ba, t[rt].ba), t[p].bb = std::min(t[p].bb, t[rt].bb);
    }
    if (lt && rt)
        t[p].u = std::min({ t[p].u, t[lt].ba + t[rt].aa, t[lt].ab + t[rt].bb });
    return;
}
int adda(int p, long long l, long long r, int x, int a, int b) {
    if (!p)
        p = ++tot, t.emplace_back(), t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
    if (l == r) {
        if (!t[p].id)
            t[p].id = ++cnt, aa.emplace_back(), ab.emplace_back(), ba.emplace_back(), bb.emplace_back();
        int id = t[p].id;
        aa[id].insert(a), ab[id].insert(b);
        t[p].aa = *aa[id].begin(), t[p].ab = *ab[id].begin();
        if (!aa[id].empty() && !ba[id].empty())
            t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
        else
            t[p].u = inf;
        return p;
    }
    long long mid = (l + r) >> 1;
    if (x <= mid) {
        auto s(adda(lt, l, mid, x, a, b));
        lt = s;
    }
    else {
        auto s(adda(rt, mid + 1, r, x, a, b));
        rt = s;
    }
    pushup(p);
    return p;
}
int addb(int p, long long l, long long r, int x, int a, int b) {
    if (!p)
        p = ++tot, t.emplace_back(), t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
    if (l == r) {
        if (!t[p].id)
            t[p].id = ++cnt, aa.emplace_back(), ab.emplace_back(), ba.emplace_back(), bb.emplace_back();
        int id = t[p].id;
        ba[id].insert(a), bb[id].insert(b);
        t[p].ba = *ba[id].begin(), t[p].bb = *bb[id].begin();
        if (!aa[id].empty() && !ba[id].empty())
            t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
        else
            t[p].u = inf;
        return p;
    }
    long long mid = (l + r) >> 1;
    if (x <= mid) {
        auto s(addb(lt, l, mid, x, a, b));
        lt = s;
    }
    else {
        auto s(addb(rt, mid + 1, r, x, a, b));
        rt = s;
    }
    pushup(p);
    return p;
}
void dela(int p, long long l, long long r, int x, int a, int b) {
    if (l == r) {
        int id = t[p].id;
        aa[id].erase(aa[id].find(a)), ab[id].erase(ab[id].find(b));
        t[p].aa = (aa[id].empty() ? inf : *aa[id].begin());
        t[p].ab = (ab[id].empty() ? inf : *ab[id].begin());
        if (!aa[id].empty() && !ba[id].empty())
            t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
        else
            t[p].u = inf;
        return;
    }
    long long mid = (l + r) >> 1;
    if (x <= mid)
        dela(lt, l, mid, x, a, b);
    else
        dela(rt, mid + 1, r, x, a, b);
    pushup(p);
    return;
}
void delb(int p, long long l, long long r, int x, int a, int b) {
    if (l == r) {
        int id = t[p].id;
        ba[id].erase(ba[id].find(a)), bb[id].erase(bb[id].find(b));
        t[p].ba = (ba[id].empty() ? inf : *ba[id].begin());
        t[p].bb = (bb[id].empty() ? inf : *bb[id].begin());
        if (!aa[id].empty() && !ba[id].empty())
            t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
        else
            t[p].u = inf;
        return;
    }
    long long mid = (l + r) >> 1;
    if (x <= mid)
        delb(lt, l, mid, x, a, b);
    else
        delb(rt, mid + 1, r, x, a, b);
    pushup(p);
    return;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    std::freopen("set.in", "r", stdin);
    std::freopen("set.out", "w", stdout);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int q, rt = 0;
    std::cin >> q;
    for (int i = 1; i <= q; ++i) {
        int op, d, a, b;
        std::cin >> op >> d >> a >> b;
        if (op == 0 && d == 0)
            dela(rt, -inf, inf, a - b, a, b);
        else if (op == 0)
            delb(rt, -inf, inf, b - a, a, b);
        else if (d == 0)
            rt = adda(rt, -inf, inf, a - b, a, b);
        else
            rt = addb(rt, -inf, inf, b - a, a, b);
        std::cout << (t[1].u == inf ? -1 : t[1].u) << '\n';
    }
    return 0;
}

青蛙题

http://222.180.160.110:61235/contest/6010/problem/1

全程都是被牵着鼻子走捏。自己的大脑完全没有运转捏。开摆!

llsw:哎其实 碰到这种区间里面找区间的问题的话 扫描线 算是常见思路了

我们会发现想到区间种类数我们会有几种思路:集合哈希、前驱后继 + 人类智慧、莫队之类的。这道题感觉是可以用集合哈希做的,但是看了一眼原题出自 Ynoi,哈哈,这道题感觉是不能用集合哈希做的 流泪

大致思路是,对于 \(i=1\sim n\),依次考虑 \(i\) 作为右端点的情况。线段树维护每个 \(j\) 作为左端点时的 \(i-r_j\),其中 \([j, r_j]\) 是与 \([j,i]\) 种类相同的最小区间。

那么询问的时候,只需要找到最大的 \(j'\),满足 \([j, r]\)\([l, r]\) 种类相同,求解 \([l, j']\) 的区间和即可。怎么找到 \(j'\) 呢?这里就用到了前驱后继 + 人类智慧法。初始每个 \(l\) 对应的 \(j'\) 就是自己,若加入了一个与 \(l\) 相同的新元素,那么 \(l\) 就不再有贡献,此时 \(l\)\(j'\) 就会继承 \(l+1\)\(j'\),这个过程用并查集即可简单维护。

#include <bits/stdc++.h>
const int lim = 2e6;
const int maxn = 2e6 + 5;
const int maxm = 5e7 + 5;
const int inf = 0x3f3f3f3f;
struct { int l, r, u, d; } t[maxn << 2];
int tot;
#define lt (p << 1)
#define rt (lt | 1)
void pushdown(int p) {
    if (~t[p].d) {
        t[lt].d = t[rt].d = t[p].d;
        t[lt].u = t[p].d - t[lt].r + 1;
        t[rt].u = t[p].d - t[rt].r + 1;
        t[p].d = -1;
    }
    return;
}
void bld(int p, int l, int r) {
    t[p].l = l, t[p].r = r, t[p].d = -1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    bld(lt, l, mid), bld(rt, mid + 1, r);
    return;
}
void upd(int p, int l, int r, int v) {
    if (l <= t[p].l && t[p].r <= r) {
        t[p].d = v, t[p].u = v - t[p].r + 1;
        return;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid)
        upd(lt, l, r, v);
    if (r > mid)
        upd(rt, l, r, v);
    t[p].u = std::min(t[lt].u, t[rt].u);
    return;
}
int ask(int p, int l, int r) {
    if (l <= t[p].l && t[p].r <= r)
        return t[p].u;
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1, res = inf;
    if (l <= mid)
        res = ask(lt, l, r);
    if (r > mid)
        res = std::min(res, ask(rt, l, r));
    return res;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int n, q;
    std::cin >> n;
    std::vector<int> a(n + 1), la(lim + 1), pre(n + 1), f(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        pre[i] = la[a[i]], la[a[i]] = i, f[i] = i;
    }
    std::cin >> q;
    std::vector<int> res(q + 1);
    std::vector<std::vector<std::pair<int, int> > > t(n + 1);
    for (int i = 1, l, r; i <= q; ++i) {
        std::cin >> l >> r;
        t[r].emplace_back(l, i);
    }
    bld(1, 1, n);
    std::function<int(int)> find = [&](int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    };
    auto merge = [&](int x, int y) {
        x = find(x), y = find(y);
        f[std::min(x, y)] = std::max(x, y);
        return;
    };
    for (int r = 1; r <= n; ++r) {
        if (pre[r])
            merge(pre[r], pre[r] + 1);
        upd(1, pre[r] + 1, r, r);
        for (auto [l, i] : t[r])
            res[i] = ask(1, l, find(l));
    }
    for (int i = 1; i <= q; ++i)
        std::cout << res[i] << '\n';
    return 0;
}

一言 - Hitokoto