CF1000F One Occurrence 题解

怎么都在写根号做法？

莫队做法有点过于无脑了。

另外突然发现我之前因为和别人朝 inline 有没有用的时候交了一发这题的代码测了一下，结论是 inline 似乎确实有用。然后我以为自己做过这个题目直接交了。

讲下我的 做法。

首先判断是否有解是容易的，直接扫描线即可。但是我们要输出一个数！怎么办？

考虑一个数的可行区间。显然满足以下两个条件。

其中 表示当前这个数上一次出现的时候， 表示下一次出现的时候。

我们对右端点扫描线。我们发现我们需要对一个区间加入和删除 tag，并且 tag 之间有交换律（因为最后输出的哪个数其实并不重要，只需要是出现恰好一次的数就行），这个可以使用标记永久化来轻松维护。参见 AT_abc342_g。复杂度 。

进一步发现，如果有多个标记，我们只需要保存删除时间最靠后的标记即可，不需要保存所有的标记，只需要在标记上额外维护一个过期时间的信息即可，仍然可以标记永久化。单点查询的时候查到一个方案就可以 return 了。复杂度 ，并且跑不满。

代码也很好写，只需要写建树/合并标记就行了。

▶

INFO 参考代码

#include <iostream>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace ds {
    constexpr uint lc(uint x) { return x * 2; };
    constexpr uint rc(uint x) { return x * 2 + 1; }

    struct segtree {
        struct info_t {
            uint color;
            uint latest_time;

            info_t() : color(0), latest_time(0) {}
            info_t(uint _color, uint _latest_time)
                : color(_color), latest_time(_latest_time) {}
        };

        struct node {
            uint l, r;
            info_t info;

            uint mid() const { return (l + r) / 2; }

            void apply(const info_t &new_info) {
                if (new_info.latest_time >= info.latest_time) {
                    info = new_info;
                }
            }
        };

        std::vector<node> t;

        void build(uint l, uint r, uint p) {
            t[p].l = l;
            t[p].r = r;
            if (l + 1 == r) {
                return;
            }
            uint mid = t[p].mid();
            build(l, mid, lc(p));
            build(mid, r, rc(p));
            return;
        }

        segtree(uint n) : t(n * 4) { build(0, n, 1); }

        void apply(uint l, uint r, const info_t &info, uint p = 1) {
            if (l <= t[p].l && t[p].r <= r) {
                t[p].apply(info);
                return;
            }
            uint mid = t[p].mid();
            if (l < mid) {
                apply(l, r, info, lc(p));
            }
            if (mid < r) {
                apply(l, r, info, rc(p));
            }
            return;
        }

        uint query(uint pos, uint cur_time, uint p = 1) const {
            if (t[p].info.latest_time >= cur_time) {
                return t[p].info.color;
            }
            if (t[p].l + 1 == t[p].r) {
                return 0;
            }
            uint mid = t[p].mid();
            if (pos < mid) {
                return query(pos, cur_time, lc(p));
            }
            else {
                return query(pos, cur_time, rc(p));
            }
        }
    };

} // namespace ds

const uint npos = -1;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    uint n;
    std::cin >> n;
    std::vector<uint> v(n);
    std::vector<std::pair<uint, uint>> alive_range(n);
    for (size_t i = 0; i < n; i++) {
        std::cin >> v[i];
        alive_range[i].first = 0;
        alive_range[i].second = n;
    }
    {
        std::vector<uint> appear(5e5 + 1, npos);
        for (size_t i = 0; i < n; i++) {
            alive_range[i].first = appear[v[i]] + 1;
            appear[v[i]] = i;
        }
        appear.assign(5e5 + 1, n);
        for (int i = n - 1; i >= 0; i--) {
            alive_range[i].second = appear[v[i]];
            appear[v[i]] = i;
        }
    }
    uint q;
    std::cin >> q;
    std::vector<uint> ans(q);
    std::vector<std::vector<std::pair<uint, uint>>> query(n +
                                                          1); // 左端点，下标。
    for (size_t i = 0; i < q; i++) {
        uint l, r;
        std::cin >> l >> r;
        l--;
        query[r].push_back({l, i});
    }
    ds::segtree sgt(n);
    for (size_t i = 0; i < n; i++) {
        for (auto &&cur_query : query[i]) {
            ans[cur_query.second] = sgt.query(cur_query.first, i);
        }
        sgt.apply(alive_range[i].first, i + 1,
                  ds::segtree::info_t{v[i], alive_range[i].second});
    }
    for (auto &&cur_query : query[n]) {
        ans[cur_query.second] = sgt.query(cur_query.first, n);
    }
    for (size_t i = 0; i < q; i++) {
        std::cout << ans[i] << "\n";
    }
    std::cout << std::flush;
    return 0;
}

/**
 * 这个真有原吧。
 *
 * 别放扫描线模板了。
 *
 * P3582.P7764.
 *
 * wc 你怎么要输出数啊。
 *
 * 我想想。这个 matter 吗。
 *
 * 我可以快速判断一个数是否出现了两次。
 *
 * 我是不是需要区间覆盖。别急。
 *
 * 我们对于每个位置，维护当前这个位置上一个和下一个出现的位置。
 *
 * 我们需要：加入标记 删除标记。
 *
 * 我们可以使用标记永久化来实现。
 *
 * 这个，也有原题。AT_abc342_g。
 *
 * 到底是谁在写根号做法？？
 *
 * 反正能过。我们只需要维护时间最考后的那个标记即可做到单 log。
 *
 * 不需要 update。什么都不需要。
 *
 * 怎么 wa 了。
 *
 * grader！启动！
 * 
 * okok。
 * 
 * 开个快读。
 *
 * 875！我看谁敢黑单 log 算法！
 */

我真得睡觉了。下次再也不熬夜了。