这题的数据能用跳表过吗，理论应该可以的吧，MLE 5个点

winterl @ 2024-09-10 13:33:45

#include <iostream>
#include <limits>
#include <random>
#include <stdexcept>
#include <string>
#include <vector>

template <typename T, size_t kMaxLevel = 16> class Skiplist {
    struct Node {
        T Key;
        std::vector<size_t> SkipSpans;
        std::vector<Node *> Nexts;
        Node(const T &key, const size_t &size)
            : Key(key), SkipSpans(size + 1, 0), Nexts(size + 1, nullptr) {}
    };
    std::bernoulli_distribution rand_;
    std::minstd_rand seed{std::random_device{}()};
    size_t count_ = 0;
    Node *head_ = new Node(std::numeric_limits<T>::min(), kMaxLevel);

    size_t random_level() {
        size_t level = 1;
        while (level < kMaxLevel and rand_(seed))
            level++;
        return level;
    }

    std::pair<std::vector<Node *>, std::vector<size_t>>
    search_updates(const T &item) {
        std::vector<Node *> updates(kMaxLevel + 1);
        auto current = head_;
        std::vector<size_t> totalSpans(kMaxLevel + 2, 0);
        for (auto level = kMaxLevel; level != -1; --level) {
            totalSpans[level] = totalSpans[level + 1];
            while (current->Nexts[level] and
                   current->Nexts[level]->Key < item) {
                totalSpans[level] += current->SkipSpans[level];
                current = current->Nexts[level];
            }
            updates[level] = current;
        }
        return {updates, totalSpans};
    }

    Node *lower_bound(const T &item) {
        auto current = head_;
        for (auto level = kMaxLevel; level != -1; --level)
            while (current->Nexts[level] and current->Nexts[level]->Key < item)
                current = current->Nexts[level];
        return current;
    }

    Node *upper_bound(const T &item) {
        auto current = head_;
        for (auto level = kMaxLevel; level != -1; --level)
            while (current->Nexts[level] and current->Nexts[level]->Key <= item)
                current = current->Nexts[level];
        return current;
    }

  public:
    bool empty() { return count_ == 0; }
    size_t size() { return count_; }

    void add(const T &item) {
        auto [updates, totalSpans] = search_updates(item);
        auto level = random_level();
        auto newNode = new Node(item, level);
        if (newNode == nullptr)
            throw std::bad_alloc();
        const auto totalSpan = totalSpans.front() + 1;
        for (size_t currentLevel = 0; currentLevel <= level; ++currentLevel) {
            newNode->Nexts[currentLevel] =
                updates[currentLevel]->Nexts[currentLevel];
            updates[currentLevel]->Nexts[currentLevel] = newNode;
            auto diff = totalSpan - totalSpans[currentLevel];
            if (newNode->Nexts[currentLevel])
                newNode->SkipSpans[currentLevel] =
                    updates[currentLevel]->SkipSpans[currentLevel] - diff + 1;
            updates[currentLevel]->SkipSpans[currentLevel] = diff;
        }
        // 记得处理在高层前插入低层的情况的 skipSpan
        for (auto currentLevel = level + 1; currentLevel <= kMaxLevel;
             ++currentLevel)
            if (updates[currentLevel]->Nexts[currentLevel])
                updates[currentLevel]->SkipSpans[currentLevel]++;
        count_++;
    }

    bool erase(const T &item) {
        if (empty())
            return false;
        auto updates = search_updates(item).first;
        auto node = updates.front()->Nexts.front();
        if (node == nullptr or node->Key != item)
            return false;
        for (size_t currentLevel = 0; currentLevel < node->Nexts.size();
             ++currentLevel) {
            if (updates[currentLevel]->Nexts[currentLevel] != node)
                continue;
            updates[currentLevel]->Nexts[currentLevel] =
                node->Nexts[currentLevel];
            if (updates[currentLevel]->Nexts[currentLevel])
                updates[currentLevel]->SkipSpans[currentLevel] +=
                    node->SkipSpans[currentLevel] - 1;
            else
                updates[currentLevel]->SkipSpans[currentLevel] = 0;
        }
        // 记得处理在高层前删除低层的情况的 skipSpan
        for (auto currentLevel = node->Nexts.size(); currentLevel <= kMaxLevel;
             ++currentLevel)
            if (updates[currentLevel]->Nexts[currentLevel])
                updates[currentLevel]->SkipSpans[currentLevel]--;
        delete node;
        count_--;
        return true;
    }

    bool search(const T &item) {
        auto updates = search_updates(item).first;
        auto node = updates.front()->Nexts.front();
        return node and node->Key == item;
    }

    size_t rank_of(const T &item) {
        return search_updates(item).second.front() + 1;
    }

    T get_by_rank(const size_t &rank) {
        if (rank > count_)
            throw std::out_of_range("rank can't not greater than list size");
        size_t currentRank = 0;
        auto current = head_;
        for (auto currentLevel = kMaxLevel; currentLevel != -1; --currentLevel)
            while (current->Nexts[currentLevel] and
                   current->SkipSpans[currentLevel] + currentRank <= rank) {
                currentRank += current->SkipSpans[currentLevel];
                current = current->Nexts[currentLevel];
            }
        return current->Key;
    }

    T lower_to(const T &item) { return lower_bound(item)->Key; }

    T upper_to(const T &item) { return upper_bound(item)->Nexts[0]->Key; }

    class iterator {
        Node *current_;

      public:
        iterator(Node *start) : current_(start) {}
        T &operator*() { return current_->Key; }
        iterator &operator++() {
            current_ = current_->Nexts[0];
            return *this;
        }
        bool operator!=(const iterator &other) const {
            return current_ != other.current_;
        }
    };
    iterator begin() const { return iterator(head_->Nexts[0]); }
    iterator end() const { return iterator(nullptr); }

    void makeView() {

        std::endl(std::cout);
        for (auto current = head_; current != nullptr;
             current = current->Nexts[0]) {
            for (size_t i = 0; i < current->Nexts.size(); ++i)
                std::cout << current->Key << '['
                          << (current->Nexts[i]
                                  ? std::to_string(current->Nexts[i]->Key)
                                  : "nullptr")
                          << "](" << current->SkipSpans[i] << ") ";
            std::endl(std::cout);
        }
        std::endl(std::cout);
    }

    Skiplist(const double &p = 0.5) : rand_(p) {}

    ~Skiplist() {
        auto current = head_;
        while (current) {
            auto next = current->Nexts[0];
            delete current;
            current = next;
        }
    }
};

namespace std {
std::ostream &endl(std::ostream &os) { return os.put('\n'); }
} // namespace std

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::int64_t n, m, opt, x, answer{}, last{};
    std::cin >> n >> m;
    Skiplist<std::int64_t> lst;
    for (std::int64_t x; n--;) {
        std::cin >> x;
        lst.add(x);
    }
    while (m--) {
        std::cin >> opt >> x;
        x ^= last;
        switch (opt) {
        case 1:
            lst.add(x);
            break;
        case 2:
            lst.erase(x);
            break;
        case 3:
            last = lst.rank_of(x);
            break;
        case 4:
            last = lst.get_by_rank(x);
            break;
        case 5:
            last = lst.lower_to(x);
            break;
        case 6:
            last = lst.upper_to(x);
            break;
        }
        if (opt > 2)
            answer ^= last;
    }
    std::cout << answer << std::endl;
    return 0;
}

by CodingJellyfish @ 2024-09-13 20:01:48

能，前提是你不要把vector直接放节点里，vector 一个12字节

by winterl @ 2024-11-04 19:25:10

@CodingJellyfish 试试用了 new int[]，手动管理内存，还是会 MLE 5个点，是不是还有可以优化的空间

#include <cstdint>
#include <iostream>
#include <limits>
#include <random>
#include <stdexcept>
#include <string>

template<typename T, size_t kMaxLevel = 16>
class Skiplist {
    struct Node {
        T Key;
        size_t *SkipSpans;
        Node **Nexts;
        const uint8_t height;

        Node(const T &key, const size_t &size)
                : Key(key), height(size + 1) {
            //SkipSpans(size + 1, 0), Nexts(size + 1, nullptr) {
            SkipSpans = new size_t[size + 1];
            std::fill(SkipSpans, SkipSpans + size + 1, 0);
            Nexts = new Node *[size + 1];
            std::fill(Nexts, Nexts + size + 1, nullptr);
        }

        ~Node() {
            delete[]SkipSpans;
            delete[]Nexts;
        }
    };

    std::bernoulli_distribution rand_;
    std::minstd_rand seed_{std::random_device{}()};
    size_t count_ = 0;
    Node *head_ = new Node(std::numeric_limits<T>::min(), kMaxLevel);

    size_t random_level() {
        size_t level = 1;
        while (level < kMaxLevel and rand_(seed_))
            level++;
        return level;
    }

//    std::pair<std::vector<Node *>, std::vector<size_t>>
    std::pair<Node **, size_t *> search_updates(const T &item) {
        Node **updates = new Node *[kMaxLevel + 1];
//        std::vector<Node *> updates(kMaxLevel + 1);
        auto current = head_;
        size_t *totalSpans = new size_t[kMaxLevel + 2];
        std::fill(totalSpans, totalSpans + kMaxLevel + 2, 0);
//        std::vector<size_t> totalSpans(kMaxLevel + 2, 0);
        for (auto level = kMaxLevel; level != -1; --level) {
            totalSpans[level] = totalSpans[level + 1];
            while (current->Nexts[level] and
                   current->Nexts[level]->Key < item) {
                totalSpans[level] += current->SkipSpans[level];
                current = current->Nexts[level];
            }
            updates[level] = current;
        }
        return {updates, totalSpans};
    }

    Node *lower_bound(const T &item) {
        auto current = head_;
        for (auto level = kMaxLevel; level != -1; --level)
            while (current->Nexts[level] and current->Nexts[level]->Key < item)
                current = current->Nexts[level];
        return current;
    }

    Node *upper_bound(const T &item) {
        auto current = head_;
        for (auto level = kMaxLevel; level != -1; --level)
            while (current->Nexts[level] and current->Nexts[level]->Key <= item)
                current = current->Nexts[level];
        return current;
    }

public:
    bool empty() { return count_ == 0; }

    size_t size() { return count_; }

    void add(const T &item) {
        auto &&[updates, totalSpans] = search_updates(item);
        auto level = random_level();
        auto newNode = new Node(item, level);
        if (newNode == nullptr)
            throw std::bad_alloc();
        const auto totalSpan = totalSpans[0] + 1;
        for (size_t currentLevel = 0; currentLevel <= level; ++currentLevel) {
            newNode->Nexts[currentLevel] =
                    updates[currentLevel]->Nexts[currentLevel];
            updates[currentLevel]->Nexts[currentLevel] = newNode;
            auto diff = totalSpan - totalSpans[currentLevel];
            if (newNode->Nexts[currentLevel])
                newNode->SkipSpans[currentLevel] =
                        updates[currentLevel]->SkipSpans[currentLevel] - diff + 1;
            updates[currentLevel]->SkipSpans[currentLevel] = diff;
        }
        // 记得处理在高层前插入低层的情况的 skipSpan
        for (auto currentLevel = level + 1; currentLevel <= kMaxLevel;
             ++currentLevel)
            if (updates[currentLevel]->Nexts[currentLevel])
                updates[currentLevel]->SkipSpans[currentLevel]++;
        delete[]updates;
        delete[]totalSpans;
        count_++;
    }

    bool erase(const T &item) {
        if (empty())
            return false;
        auto &&[updates, totalSpans] = search_updates(item);
        auto node = updates[0]->Nexts[0];
        if (node == nullptr or node->Key != item)
            return false;
        for (size_t currentLevel = 0; currentLevel < node->height;
             ++currentLevel) {
            if (updates[currentLevel]->Nexts[currentLevel] != node)
                continue;
            updates[currentLevel]->Nexts[currentLevel] =
                    node->Nexts[currentLevel];
            if (updates[currentLevel]->Nexts[currentLevel])
                updates[currentLevel]->SkipSpans[currentLevel] +=
                        node->SkipSpans[currentLevel] - 1;
            else
                updates[currentLevel]->SkipSpans[currentLevel] = 0;
        }
        // 记得处理在高层前删除低层的情况的 skipSpan
        for (auto currentLevel = node->height; currentLevel <= kMaxLevel;
             ++currentLevel)
            if (updates[currentLevel]->Nexts[currentLevel])
                updates[currentLevel]->SkipSpans[currentLevel]--;
        delete node;
        delete[]updates;
        delete[]totalSpans;
        count_--;
        return true;
    }

    bool search(const T &item) {
        auto updates = search_updates(item).first;
        auto node = updates.front()->Nexts.front();
        return node and node->Key == item;
    }

    size_t rank_of(const T &item) {
        auto &&[updates, totalSpans] = search_updates(item);
        auto result = totalSpans[0] + 1;
        delete[]updates;
        delete[]totalSpans;
        return result;
    }

    T nth_element(const size_t &rank) {
        if (rank > count_)
            throw std::out_of_range("rank can't not greater than list size");
        size_t currentRank = 0;
        auto current = head_;
        for (auto currentLevel = kMaxLevel; currentLevel != -1; --currentLevel)
            while (current->Nexts[currentLevel] and
                   current->SkipSpans[currentLevel] + currentRank <= rank) {
                currentRank += current->SkipSpans[currentLevel];
                current = current->Nexts[currentLevel];
            }
        return current->Key;
    }

    T lower_to(const T &item) { return lower_bound(item)->Key; }

    T upper_to(const T &item) { return upper_bound(item)->Nexts[0]->Key; }

    class iterator {
        Node *current_;

    public:
        iterator(Node *start) : current_(start) {}

        T &operator*() { return current_->Key; }

        iterator &operator++() {
            current_ = current_->Nexts[0];
            return *this;
        }

        bool operator!=(const iterator &other) const {
            return current_ != other.current_;
        }
    };

    iterator begin() const { return iterator(head_->Nexts[0]); }

    iterator end() const { return iterator(nullptr); }

    void makeView() {

        std::endl(std::cout);
        for (auto current = head_; current != nullptr;
             current = current->Nexts[0]) {
            for (size_t i = 0; i < current->height; ++i)
                std::cout << current->Key << '['
                          << (current->Nexts[i]
                              ? std::to_string(current->Nexts[i]->Key)
                              : "nullptr")
                          << "](" << current->SkipSpans[i] << ") ";
            std::endl(std::cout);
        }
        std::endl(std::cout);
    }

    Skiplist(const double &p = 0.5) : rand_(p) {}

    ~Skiplist() {
        auto current = head_;
        while (current) {
            auto next = current->Nexts[0];
            delete current;
            current = next;
        }
    }
};

namespace std {
    std::ostream &endl(std::ostream &os) { return os.put('\n'); }
} // namespace std

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int64_t n, m, opt, x, answer{}, last{};
    std::cin >> n >> m;
    Skiplist<std::int32_t, 8> lst(0.25);
    while (n--) {
        std::cin >> x;
        lst.add(x);
    }
    std::pair<int, int> a{1, 2};
    auto &&[xx, yy] = a;
    while (m--) {
        std::cin >> opt >> x;
        x ^= last;
        switch (opt) {
            case 1:
                lst.add(x);
                break;
            case 2:
                lst.erase(x);
                break;
            case 3:
                last = lst.rank_of(x);
                break;
            case 4:
                last = lst.nth_element(x);
                break;
            case 5:
                last = lst.lower_to(x);
                break;
            case 6:
                last = lst.upper_to(x);
                break;
        }
        if (opt > 2)
            answer ^= last;
    }
    std::cout << answer << std::endl;

    return 0;
}

by CodingJellyfish @ 2024-12-31 01:02:28

那就不要用指针了吧，Node* 换成数组下标内存能小一半